Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.
Process the following $Q$ queries in order. In the $i$-th query, you are given $K_i,X_i,M_i$. Perform the following operation $K_i$ times, and then output $A_{X_i}$ modulo $998244353$.

• Let $x$ be the minimum element of $A$. Take the $M_i$ smallest integers that are at least $x$ and are not contained in $A$, arrange them in ascending order, and let this sequence be the new $A$.

Note that changes made by a query carry over to the next query.

Constraints

• All input values are integers.
• $1\le N\le 3000$
• $1\le Q\le 3000$
• $1\le A_i\le 10^9\quad(1\le i\le N)$
• $1\le K_i\le 10^9\quad(1\le i\le Q)$
• $1\le X_i\le M_i\le 10^9\quad(1\le i\le Q)$

This problem also has evil cases with harder constraints, which are as follows.

• All input values are integers.
• $1\le N\le 10^5$
• $1\le Q\le 10^5$
• $1\le A_i\le 10^9\quad(1\le i\le N)$
• $1\le K_i\le 10^9\quad(1\le i\le Q)$
• $1\le X_i\le M_i\le 10^9\quad(1\le i\le Q)$

The evil cases are judged, but they do not affect the final verdict. Try them if you have energy to spare.

Input

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$K_1$ $X_1$ $M_1$
$K_2$ $X_2$ $M_2$
$\vdots$
$K_Q$ $X_Q$ $M_Q$

Output

Output $Q$ lines. The $i$-th line should contain the result of the $i$-th query.

Sample

4 3
1 2 4 6
1 1 4
1 1 4
3 5 5

3
4
15

10 10
72494724 256674714 313253426 599214029 902475449 996684696 34537839 225932543 731286711 851529395
618714061 21048135 53392932
778865009 406678109 416530079
477052802 147454770 351371372
671921386 80856595 551118804
333685095 152683213 820558853
744767085 204695052 257535314
833792916 325319475 758974079
829827121 250824565 424363265
966042025 20697527 326806538
689910103 44003903 519864118

784341550
857264411
307360820
109013452
816875714
571870008
872854725
757551548
492602093
445025261