2d Segment Tree
hard
Mr. Pepcoder has a 2D Array, and his Friend love to do operations on thearray. The operations can be a query or an update. For each query the Friend say four indices x1, y1, x2 and y2, and their father answers back with the sum of the elements of the rectangle whose top left index is x1, y1 and bottom right is x2, y2. When there is an update, the friend says index (x1,y1) and a value x , and Pepcoder will add x to arr[x1][y1] (so the new value of arr[x1][y1] is arr[x1][y1] + x ). Because indexing the array from zero is too obscure for friend, all indices start from 1.
Constraints
1 <= n,m <= 10^3 1 <= Q <= 10^5 1 <= x1,y1,x2,y2 <= N -10^9 <= arr[i] <= 10^9
Format
Input
The first line of the input contains n and m. The next n lines contain m integers each, the initial values of the array.Next line contains Q, the number of operations that will be made. Each of the next Q lines contains an operation. Query operations are of the form "q x1 y1 x2 y2", while update operations are of the form "u x1 x2 x".
Output
You have to print the answer for every query in a different line, in the same order of the input.
Example
Sample Input
3 3
1 2 3
4 5 6
7 8 9
5
q 1 1 2 2
q 1 2 3 3
q 2 1 3 2
u 1 1 1
q 1 1 2 2
Sample Output
12
33
24
13
