三次前缀和

题目描述

给定 $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$ 取模的值。

输入格式

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

N Q
A_1 A_2 … A_N
query_1
query_2
⋮
query_Q

每个查询以以下两种格式之一给出：

1 x v

2 x

输出格式

对于每个 2 x 查询，输出答案，每个答案占一行。

样例

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

15
9

当第 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$。

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