Problem Description

There is a sequence of length $ N $ denoted as $ X = {x_1, x_2, ..., x_N} $. We will perform $ Q $ query operations on this sequence. There are three types of query operations, as described below:

• 1 a b v ― Add the value $ v $ uniformly to the interval $ [a, b] $ of the sequence $ X $.
• 2 a b c d ― Replace the interval $ [a, b] $ of the sequence $ X $ with the values of the interval $ [c, d] $ at the time the query is called. It is guaranteed that $ b - a = d - c $. More strictly, let the resulting sequence be $ X' $, then $ X'_{a} = X_c $, $ X'_{a+1} = X_{c+1} $, ..., $ X'_{b} = X_{d} $. For indices $ j $ not in $ [a, b] $, $ X'_j = X_j $.
• 3 a b ― Calculate the sum of the values contained in the interval $ [a, b] $ of the sequence $ X $.

You must write a program that processes these queries in order.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains two integers, $N\ (1 ≦ N ≦ 2×10^5)$ representing the length of the sequence $ X $ and $Q\ (1 ≦ Q ≦ 2×10^5)$ representing the number of queries.
• The second line contains $ N $ space-separated integers, $x_i\ (-10^6 ≦ x_i ≦ 10^6)$, representing the values of the sequence $ X $.
• The following $ Q $ lines contain the queries described in the problem, in the format 1 a b v, 2 a b c d, or 3 a b. It is guaranteed that $ -10^6 ≦ v ≦ 10^6 $, $ 1 ≦ a ≦ b ≦ N $, $ 1 ≦ c ≦ d ≦ N $, and $ b - a = d - c $.

Output Format

For each query in the format 3 a b, output the answer in the given order, each on a new line.

Sample Input and Output

Sample Input #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

Sample Output #1

15
9
20

Sample Input #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

Sample Output #2

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

Notes/Hints

Sample Explanation 1

• The first query outputs the sum of $ [1, 5] $, which is $ 1 + 2 + 3 + 4 + 5 = 15 $.
• The second query adds $ 1 $ uniformly to $ [1, 3] $, resulting in $ X = {2, 3, 4, 4, 5} $.
• The third query outputs the sum of $ [1, 3] $, which is $ 2 + 3 + 4 = 9 $.
• The fourth query copies the values of $ [1, 3] $ to $ [2, 4] $, resulting in $ X = {3, 4, 4, 4, 5} $.
• The fifth query outputs the sum of $ [1, 5] $, which is $ 3 + 4 + 4 + 4 + 5 = 20 $.

见题面 Input 部分

见题面 Output 部分