Problem Statement

You are given N, Q, and $A=(A_1,\ldots,A_N)$.
Process Q queries, each of which is of one of the following two kinds:

• 1 x v: update A_x to v.
• 2 x: let $B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j$, and $D_i=\sum_{j=1}^{i}C_j$. Print D_x modulo 998244353.

Input

Input is given from Standard Input in the following format, where ${\rm query}_i$ denotes the i-th query to be processed:
N Q
$A_1 A_2 \ldots A_N$
${\rm query}_1$
${\rm query}_2$
$\vdots$
${\rm query}_Q$

Each query is given in one of the following two formats:
1 x v

2 x

Output

Print the answer to the queries, with newlines in between.

Constraints

• $1 \leq N \leq 2\times10^5$
• $1 \leq Q \leq 2\times10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq x \leq N$
• $0 \leq v \leq 10^9$
• All values in input are integers.

Sample Input 1

3 3
1 2 3
2 3
1 2 0
2 3

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.
When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0

见题面 Input 部分

见题面 Output 部分