题目描述

给出一个长度为 $n$ 的数组 $\{A\}$，由 $1$ 到 $n$ 标号，你需要维护 $m$ 个操作。

操作分为三种，输入格式为：

1 L R d，将数组中下标 $L$ 到 $R$ 的位置都加上 $d$，即对于 $L \le i \le R$，执行 $A[i]\leftarrow A[i]+d$。

2 L1 R1 L2 R2，将数组中下标为 $L_1$ 到 $R_1$ 的位置，赋值成 $L_2$ 到 $R_2$ 的值，保证 $R_1-L_1=R_2-L_2$。

换句话说先对 $0 \le i \le R_2-L_2$ 执行 $B_i\leftarrow A_{L_2+i}$，再对 $0 \le i \le R_1-L_1$ 执行 $A_{L_1+i}\leftarrow B_i$，其中 $\{B\}$ 为一个临时数组。

3 L R，求数组中下标 $L$ 到 $R$ 的位置的和，即求出 $\sum\limits_{i=L}^{r}A_i$。

输入格式

从标准输入读入数据。

第一行一个整数 Case，表示测试点编号，其中 Case 为 $0$ 时表示该点为样例。

第二行包含两个整数 $n,m$。保证 $1 \le n,m \le 10^5$。

第三行包含 $n$ 个整数 $A_i$，表示这个数组的初值。保证 $0 \le A_i \le 10^5$。

接下来 $m$ 每行描述一个操作，格式如问题描述所示。

对于操作中提到每个数，满足 $0 \le d \le 10^5$，$1 \le L \le R \le n$，$1 \le L_1 \le R_1 \le n$，$1 \le L_2 \le R_2 \le n$，$R_1-L_1=R_2-L_2$。

输出格式

对于每次 3 操作输出一行一个数，表示求和的结果。

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

14
18
29

提示

对于 $100\%$ 的评测用例，$1 \le n \le 10^5$，$0 \le a_i<b_i \le 10000$。