Grid Manager Operations

In this problem, you are given an n x m grid of integers. Your task is to implement a grid manager that supports two types of operations:

1. Update Operation: Update the value at a specific cell in the grid.
2. Subgrid Sum Query: Calculate the sum of all values in a subgrid defined by its top‐left and bottom‐right coordinates.

The operations are given as queries. For an update query, the input includes the position and the new value. For a subgrid sum query, the input includes the corners of the subgrid and you should output the sum of values in that subgrid.

The indices are 1-indexed.

The operations can be formulated as follows:

[ update(i, j, v): \text{ set } grid[i][j] = v ]

[ sumSubgrid(x_1, y_1, x_2, y_2)= \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} grid[i][j] ]

You should process the queries in the order they appear and output the result for each sum query.

inputFormat

The first line contains two integers n and m: the number of rows and columns of the grid. The next n lines each contain m integers representing the grid. The following line contains an integer q, the number of queries. Each of the next q lines represents a query in one of the following formats:

1 i j v : Update the value at cell (i, j) to v. 2 x1 y1 x2 y2 : Output the sum of the subgrid from (x1, y1) to (x2, y2) (inclusive).

Note: All indices are 1-indexed.

outputFormat

For each query of type 2 (subgrid sum query), output the sum on a new line.## sample

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

12
50