Problem Description

You are given a sequence $a$ of length $n$. You need to process the following three types of operations:

1. 1 l r means to compute $\sum\limits_{i=l}^{r} a_i$.

2. 2 l r k means to compute $\sum\limits_{i=l}^{r} {a_i}^k$.

3. 3 l r means to compute $(r-l+1)\cdot \sum\limits_{i=l}^r \left(a_i-\overline a\right)^2$, where $\overline a$ is the average of the subsequence $[l,r]$.

Output each answer modulo $998244353$.

Input Format

The first line contains two integers $n, q$, representing the length of the sequence and the number of queries.

The second line contains $n$ integers representing the sequence $a$.

The next $q$ lines each contain one operation. The format is described in the statement.

Output Format

Output a total of $q$ lines. Each line contains one integer, representing the answer to that query.

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

9
15
190
1

Hint

Sample Explanation:

For the first query, compute the sum over $[3,5]$. The answer is $4+2+3=9$.

For the second query, compute the sum over $[1,5]$. The answer is $1+5+4+2+3=15$.

For the third query, the answer is $1^3+5^3+4^3=1+125+64=190$.

For the fourth query, the average over $[2,3]$ is $\frac{5+4}{2}=4.5$. The answer is $(3-2+1)\times((5-4.5)^2+(4-4.5)^2)=2\times(0.25+0.25)=1$.

Constraints:

For $20\%$ of the testdata, $1\leq n,q,a_i\leq 100, 1\leq k\leq 3$.

For another $10\%$ of the testdata, there are only type $1$ queries.

For another $10\%$ of the testdata, there are only type $2$ queries.

For $70\%$ of the testdata, $1\leq n,q\leq 10^5$. These test points include those with only type $1$ queries and those with only type $2$ queries.

For $100\%$ of the testdata, $1\leq n,q\leq 10^6, 1\leq k\leq 20, 1\leq a_i\leq 10^9$.

It is guaranteed that the answers to all queries are integers.

The input and output for this problem are large, so be sure to use fast I/O.

Translated by ChatGPT 5