题目描述

给一个序列 $a$，长度为 $n$，你需要进行下面三种操作：

1. 1 l r 表示求 $\sum\limits_{i=l}^{r}a_i$。

2. 2 l r k 表示求 $\sum\limits_{i=l}^{r}{a_i}^k$。

3. 3 l r 表示求 $(r-l+1)\cdot \sum\limits_{i=l}^r\left(a_i-\overline a\right)^2$，其中 $\overline a$ 为序列中 $[l,r]$ 的平均数。

输出答案对 $998244353$ 取模的结果。

输入格式

第一行输入两个整数 $n,q$ 表示序列长度，询问次数。

第二行输入 $n$ 个整数表示序列 $a$。

接下来 $q$ 行，每行有一个操作，格式见题面描述。

输出格式

输出共 $q$ 行，每行输出一个整数，表示该询问的答案。

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

9
15
190
1

提示

样例解释：

第一次询问求 $[3,5]$ 的和，答案为 $4+2+3=9$。

第二次询问求 $[1,5]$ 的和，答案为 $1+5+4+2+3=15$。

第三次询问答案为 $1^3+5^3+4^3=1+125+64=190$。

第四次询问，$[2,3]$ 的平均数为 $\frac{5+4}{2}=4.5$，答案为 $(3-2+1)\times((5-4.5)^2+(4-4.5)^2)=2\times(0.25+0.25)=1$。

数据范围：

对于 $20\%$ 的数据，$1\leq n,q,a_i\leq 100,1\leq k\leq 3$。

另有 $10\%$ 的数据，只有询问 $1$。

另有 $10\%$ 的数据，只有询问 $2$。

对于 $70\%$ 的数据，$1\leq n,q\leq10^5$，这些测试点包括了只有询问 $1$ 和只有询问 $2$ 的测试点。

对于 $100\%$ 的数据，$1\leq n,q\leq10^6,1\leq k\leq 20,1\leq a_i\leq10^9$。

保证所有询问的答案都是整数。

本题输入输出数据较大，请务必使用较快的读入输出方式。