問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
以下のクエリを順に $Q$ 個処理してください。 $i$ 番目のクエリでは $K_i,X_i,M_i$ が与えられるので、以下の操作を $K_i$ 回行った後に $A_{X_i}$ を $998244353$ で割った余りを出力してください。

• $A$ の要素の最小値を $x$ として、 $A$ に含まれない $x$ 以上の整数のうち小さい方から $M_i$ 個を順に並べた数列を新たに $A$ とする。

クエリで変更されたものは次のクエリに引き継がれることに注意してください。

制約

• 入力は全て整数
• $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)$

この問題にはより高難易度の制約である evil ケースが用意されており、その制約は以下の通りです。

• 入力は全て整数
• $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)$

evil ケースのジャッジは行われますが、最終的な判定には影響されません。余力があれば挑戦してみてください。

入力

$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$

出力

$Q$ 行出力してください。 $i$ 行目には $i$ 番目のクエリの結果を出力してください。

サンプル

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