This problem is a Mooshak version of a SPOJ Problem.

[PC024] Matrix Summation

A \(N \times N\) matrix is filled with numbers. BuggyD is analyzing the matrix, and he wants the sum of certain submatrices every now and then, so he wants a system where he can get his results from a query. Also, the matrix is dynamic, and the value of any cell can be changed with a command in such a system.

Assume that initially, all the cells of the matrix are filled with 0. Design such a system for BuggyD. Read the input format for further details.

Input

The first line contains a single integer \(N\), denoting the size of the matrix.

A list of commands follows, which will be in one of the following three formats:

• SET x y num - Set the value at cell \((x, y)\) to \(num \).
• SUM x1 y1 x2 y2 - Find and print the sum of the values in the rectangle from \((x1, y1)\) to \((x2, y2)\), inclusive. You may assume that the result will fit in a signed 32-bit integer.
• END - Indicates the end of the test case.

Output

Output one line for the answer to each SUM command.

Constraints

• \( 1 \leq N \leq 1024 \)
• \( 0 \leq x,y \lt N \)
• \( 0 \leq x1 \leq x2 \lt N \)
• \( 0 \leq y1 \leq y2 \lt N \)

There will be at most \(100\,000\) commands.

4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END

1
12
12
13