Prefix Sum Queries on a 2D Grid

You are given a two-dimensional grid of integers with ( n ) rows and ( m ) columns. Your task is to process ( q ) queries on the grid. There are two types of queries:

1. Update Query: Given four integers ( 1\ x\ y\ val ), update the value at position ( (x, y) ) (1-indexed) to ( val ).
2. Sum Query: Given five integers ( 2\ x_1\ y_1\ x_2\ y_2 ), output the sum of numbers in the subgrid defined by the top-left ( (x_1,y_1) ) and bottom-right ( (x_2,y_2) ) corners.

To achieve an efficient solution, consider using a prefix sum technique. The prefix sum array ( P ) is defined as follows: [ P(i,j)=\sum_{a=1}^{i}\sum_{b=1}^{j} grid[a][b] ] The sum of any subgrid can be computed using the formula: [ SUM = P(x_2,y_2) - P(x_1-1,y_2) - P(x_2, y_1-1) + P(x_1-1,y_1-1) ]

Note: All indices are 1-indexed.

It is guaranteed that the queries are valid and you must print the result of each sum query to standard output.

inputFormat

The first line contains three integers ( n ), ( m ) and ( q ) representing the number of rows, columns, and queries respectively.

The next ( n ) lines each contain ( m ) integers describing the initial grid values.

Then ( q ) lines follow, each line is a query:

• For an update query, the format is: 1 x y val
• For a sum query, the format is: 2 x1 y1 x2 y2

All inputs are read from standard input (stdin).

outputFormat

For each query of type 2 (sum query), output a single integer representing the sum of the specified subgrid on a new line. All outputs must be written to standard output (stdout).## sample

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

12
17
33
36