Butterfly Forest Operations

You are given a grid with \(N\) rows and \(M\) columns representing the population of butterflies in a forest. Each cell \(g_{ij}\) holds an integer value. You will be given \(Q\) operations to perform on the grid. There are two types of operations:

• Update Operation: The operation is given in the form: \(1\ r\ c\ k\). This means update the cell at row \(r\) and column \(c\) to the new value \(k\).
• Query Operation: The operation is given in the form: \(2\ r_1\ c_1\ r_2\ c_2\). For this operation, output the sum of all values in the submatrix defined by the top left cell \((r_1,c_1)\) and the bottom right cell \((r_2,c_2)\).

Note that the grid is 1-indexed. For each query operation, print the result on a new line.

inputFormat

The first line contains three integers (N), (M), and (Q) separated by spaces. This is followed by (N) lines, each with (M) integers representing the initial grid. Then (Q) lines follow, each line representing an operation. An update operation is formatted as: "1 r c k", and a query operation is formatted as: "2 r1 c1 r2 c2".

outputFormat

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

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

12
17
50