题目描述

给定 $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$。以模 $998244353$ 的形式打印 $D_x$。

约束条件

• $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$

输出

打印查询的答案，每行之间用换行符分隔。

示例输入1

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

示例输出1

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

2 1
998244353 998244353
2 1

示例输出2

0