Aloknath is a priest living in King's Landing. Since King Joffrey strongly hates any good soul living in his land he decides to slay Aloknath. But then Margaery convinces the King to spare Aloknath's life if he passes a test.
In the test Aloknath is given an array a and is asked to process two types of queries :
1. Given i, j (i <= j) - find sum of a[i] to a[j] and report the answer.
2. Given i and b (0 <= i < n-1) - update 2 consecutive elements a[i] and a[i+1] by +b and -b respectively.
Indexing is 0 based.

Input -
First line containing t denoting the no of test cases.
Each test case starts with n,m. n being the length of array and m the number of queries. A single line follows containing the elements of array. Then m lines follow each containing 3 integers either-
1 i j {=> for 1st type } or
2 i b {=> for 2nd type}

Output-
For each query of 1st type report the answer in a new line.

Constraints
0 < t < 10
1 < n < 10^4
0 < m < 10^3
0 < b < 10^7
0 < ai < 10^9

Example-

Input-
1
5 3
1 2 3 4 5
1 2 4
2 3 1
1 0 4
Output
12
15
Explanation-
1 2 4- a[2]+a[3]+a[4]=12
2 3 1- Array becomes- 1 2 3 5 4