Description

Given an array $\{A\}$ of length $n$, indexed from $1$ to $n$, you need to maintain $m$ operations.

There are three types of operations, with input formats as follows:

1 L R d: Add $d$ to all positions in the array with indices from $L$ to $R$. That is, for $L \le i \le R$, perform $A[i]\leftarrow A[i]+d$.

2 L1 R1 L2 R2: Assign the values of positions $L_2$ to $R_2$ to positions $L_1$ to $R_1$. It is guaranteed that $R_1-L_1=R_2-L_2$.

In other words, first perform $B_i\leftarrow A_{L_2+i}$ for $0 \le i \le R_2-L_2$, then perform $A_{L_1+i}\leftarrow B_i$ for $0 \le i \le R_1-L_1$, where $\{B\}$ is a temporary array.

3 L R: Query the sum of positions in the array with indices from $L$ to $R$, i.e., compute $\sum\limits_{i=L}^{r}A_i$.

Input Format

Read input from standard input.

The first line contains an integer Case, indicating the test point ID. When Case is $0$, it means this test point is the sample.

The second line contains two integers $n,m$. It is guaranteed that $1 \le n,m \le 10^5$.

The third line contains $n$ integers $A_i$, representing the initial values of the array. It is guaranteed that $0 \le A_i \le 10^5$.

The next $m$ lines each describe an operation, in the format shown in the problem description.

For every number mentioned in the operations, it holds that $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$, and $R_1-L_1=R_2-L_2$.

Output Format

For each operation of type $3$, output one line with one number, representing the sum result.

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

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, and $0 \le a_i<b_i \le 10000$.

Translated by ChatGPT 5