题目描述

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

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

1. $l\ r\ d$，将数组中下标 $l$ 到 $r$ 的位置都加上 $d$，即对于 $l≤i≤r$，执行 $A_i=A_i+d$。
2. $l_1\ r_1\ l_2\ r_2$，将数组中下标为 $l_1$ 到 $r_1$ 的位置，赋值成 $l_2$ 到 $r_2$的值，保证 $r_1−l_1=r_2−l_2$。换句话说先对 $0≤i≤r_2−l_2$ 执行 $B_i=A(l_2+i)$，再对 $0≤i≤r_1−l_1$ 执行 $A(l_1+i)=B_i$，其中 $B_i$ 为一个临时数组。
3. $l\ r$，求数组中下标 $l$ 到 $r$ 的位置的和，即求出$\sum_{i=1}^{r}A_i$ 。

输入描述

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

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

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

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

其中，$0≤d≤10^5，1≤l≤r≤n，1≤l_1≤r_1≤n1≤l_2≤r_2≤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