题目描述

给定一个长度为 $n$ 的序列，接下来进行 $q$ 次操作，每次操作形如：

• 操作一：给定 $l,r,x$，将区间 $[l,r]$ 内的每个 $a_i\leftarrow a_i+x$。
• 操作二：给定 $l,r$，查询

$$\sum_{l'=l}^{r}\sum_{r'=l'}^{r} \left( \left(\sum_{i=l'}^{r'} a_i\right)^2 +(r-l+2)(r'-l')a_{l'}a_{r'} \right).$$

对于所有操作二，给出对应的答案，对 $998244353$ 取模。

输入格式

本题开启强制在线。

输入的第一行包含一个整数 $\mathrm{type}$，表示强制在线参数。

输入的第二行包含两个整数 $n,q$，表示序列长度和操作次数。

接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始序列形态。

接下来 $q$ 行，每行首先输入一个整数 $op$：

• 若 $op=1$，则再输入三个整数 $l,r,x$，表示操作一；
• 若 $op=2$，则再输入两个整数 $l,r$，表示操作二。

由于本题强制在线，不妨设上一次操作二的答案为 $\mathrm{lastans}$（初始为 $0$）。

对于操作一，需要将 $l,r,x$ 均异或上 $(\mathrm{lastans}\times \mathrm{type})$ 得到真实的 $l,r,x$；对于操作二，需要将 $l,r$ 均异或上 $(\mathrm{lastans}\times \mathrm{type})$ 得到真实的 $l,r$。

注意：$\mathrm{lastans}$ 是取模之后的结果。

输出格式

输出包含若干行，对于每组操作二，输出本次询问的答案，对 $998244353$ 取模。

样例

输入

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

输出

50
600
351

数据范围

对于 $100\%$ 的数据，保证

$$\mathrm{type}\in\{0,1\},\qquad 1\le n,q\le 5\times 10^5, \qquad 0\le a_i,x<998244353.$$

测试点编号	$n\le$	$q\le$	特殊性质
$1\sim 2$	$600$		AB
$3\sim 4$	$5\times 10^3$
$5\sim 6$	$10^5$		A
$7\sim 8$	$5\times 10^5$
$9$	$10^5$		C
$10\sim 11$	$5\times 10^5$
$12$	$10^5$		D
$13\sim 14$	$5\times 10^5$
$15\sim 16$	$10^5$		无
$17\sim 18$	$3\times 10^5$
$19\sim 20$	$5\times 10^5$

特殊性质 A：保证 $\mathrm{type}=0$。

特殊性质 B：保证询问为操作一的概率为 $\frac34$，操作二的概率为 $\frac14$。

特殊性质 C：保证仅存在至多一个操作二。

特殊性质 D：保证不存在操作一。