407657: GYM102864 H Prefix Sum

We define

$$$$$$ a_{n}^{\left(k\right)} = \sum\limits_{i=1}^{n}a_{i}^{\left(k-1\right)}, k \ge 1 $$$$$$

You are given the initial sequence $$$a^{\left(0\right)}$$$, $$$k$$$ and several queries, each query satifies one of the following format:

• $$$\boldsymbol{1\ p\ q}$$$: add q to $$$a_p^{\left(0\right)}$$$
• $$$\boldsymbol{2\ l\ r}$$$: ask the value of $$$\sum_{i=l}^{r}a_{i}^{\left(k\right)}$$$

you have to answer the second type queries, each in one line. Since this value may huge, you should output this value $$$mod\ 998244353$$$.

The first line contains two integers, the length of the sequence $$$n$$$, and $$$k\left(1\le n, k\le 10^4\right)$$$.

The second line contains $$$n$$$ integers, $$$a_1^{\left(0\right)}, a_2^{\left(0\right)}, \dots, a_n^{\left(0\right)}\left(0\le a_i^{\left(0\right)}<998244353, i = 1, 2, \dots, n\right)$$$.

The third line contains an integer $$$m(1 \leq m \leq 2\times 10^5)$$$, the number of queries.

The next $$$m$$$ lines, each line contains $$$3$$$ integers "$$$1\ p\ q$$$" $$$\left(1\le p\le n, 0\le q<998244353\right)$$$ or "$$$2\ l\ r$$$" $$$\left(1\le l \le r\le n\right)$$$, represent the queries.

It is guaranteed that there is at least one "$$$2\ l\ r$$$" query.

For each "$$$2\ l\ r$$$" query, output an integer, represent the answer, each in one line.

3 2
1 3 2
4
2 1 3
1 2 1
2 1 3
2 1 1

17
20
1