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: