ストーリー

nauclhltくんは普通の累積和じゃ満足出来なくなりました。また、累積和をとる回数も並大抵のものでは満たされません。
例えば、$10^9$回累積和を取ってみるとか……

問題文

ある数列$P$の重み$K$の累積和を次を満たす長さ$|P|$の数列$Q$として定義します。

• $\displaystyle Q_i=\sum_{j=1}^i K^{i-j}P_j\ (1\leq i\leq |P|)$

ここで$|P|$は数列$P$の長さです。

長さ$N$の数列$A=(A_1, A_2, \cdots, A_N)$が与えられます。
以下の形式で与えられる$Q$個のクエリを順に処理してください。

• 1 k x: 「$A$を$A$の重み$k$の累積和で置き換える」という操作を$x$回繰り返す
• 2 x: $A_x$の値を$998244353$で割った余りを出力する

入力

$N\ Q$
$A_1\ A_2\ \cdots\ A_N$
$query_1$
$query_2$
$\vdots$
$query_Q$

各クエリは次のいずれかの形式で与えられます。

$1\ k\ x$

$2\ x$

• $1\leq N\leq 2000$
• $0\leq A_i\lt 998244353$
• $1\leq Q\leq 2000$
• 1 k xのクエリについて$1\leq k\lt 998244353, 1\leq x\leq 10^9$
• 2 xのクエリについて$1\leq x\leq N$
• 2 xのクエリは少なくとも1個以上与えられる
• 入力はすべて整数

出力

2 xの形式のクエリの個数を$m$として、$m$行出力してください。
$i(1\leq i\leq m)$行目には$i$番目のクエリに対する答えを出力してください。
最後に改行してください。

サンプル

4 3
3 1 4 1
2 3
1 2 1
2 3

4
18

3 2
1 1 2
1 3 2
2 2

7

10 2
0 9 9 8 2 4 4 3 5 3
1 998244352 998244353
2 10

3