Limits 1.5s, 512 MB

You are given an integer array, A[]A[ ] of size NN, and an integer MM. Then you have to perform a total of MM operations on the array. The operations can be of 22 types. They are:

Operation type 1:
11 LL RR XX
Add XX to each element of the sub-array [L,R][L,R]. For example, if the current array is A[]=[1,3,8,5,10,6]A[ ] = [1, 3, 8, 5, 10, 6], after performing the operation 11 22 55 33 the updated array will be A[]=[1,6,11,8,13,6]A[ ] = [1, 6, 11, 8, 13, 6].

Operation type 2:
22 LL RR
Find the summation of absolute differences between the adjacent elements of the sub-array [L,R][L,R]. More formally, find the value of ALAL+1+AL+1AL+2++AR1AR|A_L - A_{L+1}| + |A_{L+1} - A_{L+2}| + \ldots + |A_{R-1} - A_R|. Here, x|x| means absolute (non-negative) value of xx.

Input

The first line contains two space-separated integers NN and MM, the size of the array and the number of operations, respectively. The second line contains NN space-separated integers denoting the array. The ithi^{th} integer represents the ithi^{th} element, A[i]A[i] of the array. After that MM lines follow. The jthj^{th} line represents the jthj^{th} operation.

Constraints:
2N,M5×1052 \leq N,M \leq 5\times10^5
1LRN1 \leq L \leq R \leq N
107A[i],X107-10^7 \leq A[i],X \leq 10^7
In case of operation type 22, LRL \neq R.

Output

Output the answer of each operation type 22 in a separated line.

Sample

InputOutput
6 5
1 3 8 5 10 6
2 1 6
1 4 5 3
2 1 3
1 1 2 10
2 2 4
19
7
5

Submit

Login to submit.

Statistics

73% Solution Ratio
hamza05Earliest, Dec '21
nh_nayeemFastest, 0.1s
nusuBotLightest, 11 MB
fahimcp495Shortest, 1473B
Toph uses cookies. By continuing you agree to our Cookie Policy.