题目描述

$N,Q$ および $A=(A_1,\ldots,A_N)$ が与えられます。
以下のクエリを $Q$ 個処理してください。クエリは次の $2$ 種類のいずれかです。

• 1 x v : $A_x$ を $v$ に更新する。
• 2 x : $B_i=\sum_{j=1}^{i}A_j$、$C_i=\sum_{j=1}^{i}B_j$、$D_i=\sum_{j=1}^{i}C_j$ としたときの $D_x$ を $\bmod\ 998244353$ で出力する。

输入格式

入力は以下の形式で標準入力から与えられる。ここで ${\rm\ query}_i$ は $i$ 番目に処理するクエリである。

$N$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ ${\rm\ query}_1$ ${\rm\ query}_2$ $\vdots$ ${\rm\ query}_Q$

各クエリは以下の $2$ 種類のいずれかの形式で与えられる。

$1$ $x$ $v$

$2$ $x$

输出格式

クエリへの答えを改行区切りで出力せよ。

题目大意

已知一个长度为 $N$ 的序列 $A$，你需要进行$Q$ 次操作，它们是以下两种之一：

• 1. 1 x v：将 $A_x$ 改为 $v$。
• 2. 2 x：令 $B_i=\sum_{j=1}^iA_j,C_i=\sum_{j=1}^iB_j,D_i=\sum_{j=1}^iC_j$，求出 $D_x$ 对 $998244353$ 取模的结果。

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

15
9

2 1
998244353 998244353
2 1

0

提示

制約

• $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$
• 入力に含まれる値は全て整数である

Sample Explanation 1

$1$ 番目のクエリの時点で $A=(1,2,3)$ であるため、$B=(1,3,6)$、$C=(1,4,10)$、$D=(1,5,15)$ となり、$D_3=15$ です。 $3$ 番目のクエリの時点で $A=(1,0,3)$ であるため、$B=(1,1,4)$、$C=(1,2,6)$、$D=(1,3,9)$ となり、$D_3=9$ です。