当前没有测试数据。

F - 累计三次累加和

分数：500分

问题描述

给定整数$N$，$Q$和数组$A=(A_1,\ldots,A_N)$。
你需要处理$Q$个查询，每个查询有以下两种类型之一：

• 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$除以$998244353$的余数。

约束条件

• $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$
• 输入中的所有值均为整数。

---

输入

输入以以下格式从标准输入中给出，其中${\rm query}_i$表示要处理的第$i$个查询：

$N$ $Q$

$A_1$ $A_2$ $\ldots$ $A_N$

${\rm query}_1$

${\rm query}_2$

$\vdots$

${\rm query}_Q$

每个查询的格式如下：

``` $1$ $x$ $v$ ``` ``` $2$ $x$ ```

输出

将查询的答案输出，每个答案占一行。

---

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

15
9

当给出第一个查询时，$A=(1,2,3)$，所以$B=(1,3,6)$，$C=(1,4,10)$，$D=(1,5,15)$；因此，$D_3=15$。

当给出第三个查询时，$A=(1,0,3)$，所以$B=(1,1,4)$，$C=(1,2,6)$，$D=(1,3,9)$；因此，$D_3=9$。

---

2 1
998244353 998244353
2 1

0