Matrix Query and Update

Given an (N \times N) matrix of integers, you are required to process a series of queries. There are two types of queries:

1. Update Query: Change the value at a given cell ((i, j)) to a new integer (x).
2. Sum Query: Compute the sum of all elements in the submatrix defined by the top-left corner ((r_1, c_1)) and the bottom-right corner ((r_2, c_2)).

For efficient sum queries, you should maintain a prefix sum matrix. The sum of a submatrix can be computed using the formula: [ \text{sum} = P[r_2,c_2] - \begin{cases} P[r_1-1,c_2] & \text{if } r_1 > 0 \end{cases} - \begin{cases} P[r_2,c_1-1] & \text{if } c_1 > 0 \end{cases} + \begin{cases} P[r_1-1,c_1-1] & \text{if } r_1 > 0 \text{ and } c_1 > 0 \end{cases} ]

Input is read from stdin and output is printed to stdout. Make sure that the update operation maintains consistency in the prefix sum matrix.

inputFormat

The input is given in the following format:

• The first line contains an integer (N), the size of the matrix.
• The next (N) lines each contain (N) space-separated integers representing the matrix.
• The following line contains an integer (Q), the number of queries.
• Each of the next (Q) lines contains a query in one of the following formats:
  • For an update query: 1 i j x (set the element at row (i) and column (j) to (x)).
  • For a sum query: 2 r1 c1 r2 c2 (compute the sum of the submatrix from ((r1, c1)) to ((r2, c2))).

Note: All indices are 0-based.

outputFormat

For each sum query (type 2), print the computed sum on a new line to stdout.## sample

3
1 2 3
4 5 6
7 8 9
5
2 0 0 1 1
1 0 0 10
2 0 0 1 1
2 1 1 2 2
1 2 2 10

12
21
28