← 返回题目列表

AtCoder · abc256_f

I. 累计累计累计总和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你被给予 N, Q,和 A=(A_1,\ldots,A_N).
流程 Q 查询,每个查询属于以下两种类型之一:

  • 1 x v:更新 A_x to 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-st 查询已给出, A=(1,2,3),所以 应打印 B=(1,3,6), C=(1,4,10),和 D=(1,5,15);因此, D_3=15.

当 3-rd 查询已给出, 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