102565: [AtCoder]ABC256 F - Cumulative Cumulative Cumulative Sum

Problem Statement

You are given $N$, $Q$, and $A=(A_1,\ldots,A_N)$.
Process $Q$ queries, each of which is of one of the following two kinds:

• 1 x v: update $A_x$ to $v$.
• 2 x: let $B_i=\sum_{j=1}^{i}A_j$, $C_i=\sum_{j=1}^{i}B_j$, and $D_i=\sum_{j=1}^{i}C_j$. Print $D_x$ modulo $998244353$.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format, where ${\rm query}_i$ denotes the $i$-th query to be processed:

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

Each query is given in one of the following two formats:

$1$ $x$ $v$

$2$ $x$

Output

Print the answer to the queries, with newlines in between.

Sample Input 1

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

Sample Output 1

15
9

When the $1$-st query is given, $A=(1,2,3)$, so $B=(1,3,6)$, $C=(1,4,10)$, and $D=(1,5,15)$; thus, $D_3=15$.

When the $3$-rd query is given, $A=(1,0,3)$, so $B=(1,1,4)$, $C=(1,2,6)$, and $D=(1,3,9)$; thus, $D_3=9$.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0

问题描述

给你 $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$

输出

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

样例输入 1

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

样例输出 1

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

2 1
998244353 998244353
2 1

样例输出 2

0