题目描述

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

• 1 x v：将 $A_x$ 改为 $v$。
• 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$ 取模的结果。

输入格式

第一行输入 $N$ $Q$

第二行输入 $A_1$ $A_2$ $\ldots$ $A_N$

第三行输入 $Q$ 行，分别以以下格式输入。

• $1$ $x$ $v$
• $2$ $x$

输出格式

对于每个询问 $2$ 输出答案

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$

样例 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$ 。