问题描述

给定长度为 $N$ 的数列 $X={x_1,x_2,...,x_N}$，考虑对该序列进行 $Q$ 次查询操作。查询操作有 $3$ 种类型，如下所示。

• 1 a b v ― 在数列 $X$ 的区间 \[a,b\] 中的每个元素都加上相同的值 $v$。
• 2 a b c d ― 将数列 $X$ 的区间 \[a,b\] 替换为当前查询时区间 \[c,d\] 中的值。保证 $b-a=d-c$。更严格地说，假设查询操作后得到的序列为 $X'$，则 $X'_{a}=X_c$，$X'_{a+1}=X_{c+1}$，…，$X'_{b}=X_{d}$。对于不在 \[a,b\] 区间内的 $j$，有 $X'_j=X_j$。
• 3 a b ― 求数列 $X$ 区间 \[a,b\] 内的值的总和。

你需要编写一个程序按顺序处理这些查询。

输入

输入数据以以下格式从标准输入中给出。

$N$ $Q$ $x_1$ $x_2$ … $x_N$ $Query_1$ $Query_2$ : $Query_Q$

• 第 $1$ 行包含两个整数，分别表示数列 $X$ 的长度 $N (1 \leq N \leq 2×10^5)$ 和查询的次数 $Q (1 \leq Q \leq 2×10^5)$。
• 第 $2$ 行包含 $N$ 个整数，表示数列 $X$ 的第 $i$ 个元素的值 $x_i (-10^6 \leq x_i \leq 10^6)$，每个值之间用空格隔开。
• 第 $3$ 行到第 $Q+2$ 行，给出了如问题描述中所述的查询。每行以 1 a b v、2 a b c d 或 3 a b 的格式给出。保证 $-10^6 \leq v \leq 10^6$，$1 \leq a \leq b \leq N$，$1 \leq c \leq d \leq N$，$b-a = d-c$。

输出

对于每个形式为 3 a b 的查询，按照给定顺序输出答案。每个答案占一行，并进行换行。

示例输入1

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

示例输出1

15
9
20

• 第一个查询输出 \[1,5\] 区间的和，即 $1+2+3+4+5=15$。
• 第二个查询在 \[1,3\] 区间中每个元素上加 $1$，执行该操作后，$X={2,3,4,4,5}$。
• 第三个查询输出 \[1,3\] 区间的和，即 $2+3+4=9$。
• 第四个查询将 \[2,4\] 区间中的值复制到 \[1,3\] 区间，执行该操作后，$X={3,4,4,4,5}$。
• 第五个查询输出 \[1,5\] 区间的和，即 $3+4+4+4+5=20$。

示例输入2

10 30
-5 -5 -2 -1 2 -2 0 -4 2 5
2 9 10 9 10
2 3 5 2 4
1 2 10 -1
2 1 7 1 7
3 1 4
2 1 6 2 7
2 5 8 6 9
3 4 8
3 1 10
3 9 9
1 3 8 -1
2 4 9 1 6
3 2 7
1 9 10 -4
1 6 9 -5
1 4 6 -7
3 2 5
2 10 10 7 7
1 3 4 -10
3 4 9
3 8 9
2 6 7 8 9
3 3 5
3 3 9
1 2 10 -10
2 4 6 4 6
2 4 9 5 10
1 2 6 7
3 7 8
1 3 6 3

示例输出2

-20
-8
-18
1
-29
-36
-78
-18
-50
-86
-38