Given an $N\times M$ grid of integers $G$, you will be asked to perform $Q$ operations on it. Each operation is one of the following:

1. Update the integer at some $(r,c)$ to $v$.
2. Query the "staircase sum" at some $(r,c)$ with height $h$.

A "staircase sum" is defined as follows: starting at $(r,c)$, get the sum of every column from $(r,c)$ to $(r,c+h-1)$ with the first column going from $(r,c)$ to $(r-h+1,c)$ and then descending by $1$ unit of height for each subsequent column.

More formally, the "staircase sum" at some $(r,c,h)$ is equivalent to $\sum _{x=1}^h\sum _{y=1}^{h-x+1}{G}_{(r-y+1)(c+x-1)}$.

You will be asked to answer $Q$ of the operations described above. For each operation of type $2$, output the desired result.

Constraints

$1\le N,M\le 2000$

$1\le Q\le {10}^6$

$-{10}^6\le G_{ij}\le {10}^6$

$1\le r\le N$

$1\le c\le M$

Operation 1

$-{10}^6\le v\le {10}^6$

Operation 2

$h\ge 1$

$r-h+1\ge 1$

$c+h-1\le M$

Subtask 1 [30%]

$Q\le {10}^5$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input contains integers $N$, $M$, and $Q$.

The next $N$ lines of input each contain $M$ space-separated integers representing $G$.

The next $Q$ lines of input each contain $4$ space-separated integers in the format 1 r c v or 2 r c h.

Output Specification

For each type $2$ operation, output the "staircase sum" of the grid after applying any previous type $1$ operations.

Sample Input

4 4 3
6 1 0 2
1 1 1 1
2 2 2 2
3 0 3 -3
1 4 2 7
2 1 1 1
2 4 2 3

Sample Output

6
12

Explanation for Sample

The result of the final operation is obtained by adding the numbers highlighted below: