Story

nauclhlt is no longer satisfied with ordinary prefix sums. Nor can an ordinary number of prefix sum iterations satisfy him.
For example, how about taking the prefix sum $10^9$ times...

Problem Statement

We define the prefix sum with weight $K$ of a sequence $P$ as the sequence $Q$ of length $|P|$ satisfying the following.

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

Here, $|P|$ is the length of the sequence $P$.

You are given a sequence $A=(A_1, A_2, \cdots, A_N)$ of length $N$.
Process $Q$ queries of the following forms in order.

• 1 k x: Repeat the operation "replace $A$ with the prefix sum with weight $k$ of $A$" $x$ times.
• 2 x: Print the value of $A_x$ modulo $998244353$.

Input

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

Each query is given in one of the following formats.

$1\ k\ x$

$2\ x$

• $1\leq N\leq 2000$
• $0\leq A_i\lt 998244353$
• $1\leq Q\leq 2000$
• For queries of the form 1 k x, $1\leq k\lt 998244353, 1\leq x\leq 10^9$
• For queries of the form 2 x, $1\leq x\leq N$
• At least 1 query of the form 2 x is given.
• All inputs are integers.

Output

Let $m$ be the number of queries of the form 2 x, and print $m$ lines.
On the $i(1\leq i\leq m)$-th line, print the answer to the $i$-th such query.
Print a newline at the end.

Sample

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