Grid Operations with Prefix Sum Updates

You are given an (N \times N) grid with 1-indexed cells, initially filled with zeroes. Your task is to process a sequence of operations that either update a cell's value, query a single cell, or compute the sum of a subgrid. The operations are described as follows:

1. Operation of type 1: "1 i j v" updates the cell at row (i) and column (j) to value (v).

2. Operation of type 2: "2 i j" queries and outputs the current value at cell ((i, j)).

3. Operation of type 3: "3 x1 y1 x2 y2" queries the sum of the subgrid defined with top left corner ((x_1, y_1)) and bottom right corner ((x_2, y_2)). The subgrid sum can be computed using the prefix sums by the formula:
[ S = P(x_2, y_2) - P(x_1 - 1, y_2) - P(x_2, y_1 - 1) + P(x_1 - 1, y_1 - 1) ]

The operations are given in a single test case as described in the input format. Note that after every update, you should update the appropriate regions of the prefix sum array accordingly in order to support fast queries of subgrid sums.

inputFormat

The first line contains two integers (N) and (Q) where (N) is the size of the grid and (Q) is the number of operations.

Each of the next (Q) lines contains an operation in one of the following three formats:

- For update: 1 i j v
- For value query: 2 i j
- For subgrid sum query: 3 x1 y1 x2 y2

It is guaranteed that the indices provided are valid, and all values are integers.

outputFormat

For each operation of type 2 and type 3, output the result on a separate line in the order they appear.## sample

5 7
1 1 1 5
1 2 2 4
2 1 1
3 1 1 2 2
1 3 3 7
3 1 1 3 3
2 3 3

5
9
16
7