Board Query Operations

You are given an \( n \times n \) board initialized with zeros. You have to process \( q \) operations on the board. There are two types of operations:

• Update i j x: Update the cell at row i and column j to value \( x \). (The board is 1-indexed.)
• Query r1 c1 r2 c2: Compute and return the sum of all values in the submatrix defined by the top left corner \( (r_1, c_1) \) and the bottom right corner \( (r_2, c_2) \).

For example, consider a 4 × 4 board. After performing a series of updates, a query might ask for the sum of values from cell \( (1,1) \) to \( (2,2) \). The answer should be printed on a new line for each query.

Note: It is guaranteed that both the input and output are handled through standard input (stdin) and standard output (stdout).

inputFormat

The first line contains two integers, \( n \) (the dimension of the board) and \( q \) (the number of operations). The next \( q \) lines each contain an operation in one of the following two formats:

• Update i j x: Update the cell at (i, j) with value \( x \).
• Query r1 c1 r2 c2: Query the sum of the submatrix from (r1, c1) to (r2, c2).

outputFormat

For each Query operation, output the result on a new line.

## sample

4 5
Update 1 1 5
Update 2 2 3
Update 4 4 10
Query 1 1 2 2
Query 1 1 4 4

8
18

</p>