P12518 "MSTOI-R1" Easy question

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

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 a total of $q$ lines. Each line contains one integer, representing the answer to that query.

**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