Ada the Ladybug is currently doing her thesis. It is almost complete with one tiny exception - there are some graphs and statistics missing. The topic of thesis is "Behavior of Bee Hives". She examines population of bees and their growth in given areas.

Ada has all data she needs - but parsing it manually might take many long months. She decided to ask you for help. Basically - given population of individual bee hives you will have to answer the number of bees in given area. There are two kinds of queries:

• Query of kind 1 gives you coordinates of hive and number of new-born bees.
• Query of kind 2 gives you description of rectangle. You will be asked to find the number of bees living in it.

Input

The first line contains three integer numbers 1 ≤ N, M ≤ 2000, 1 ≤ Q ≤ 10⁵, the size of examined area (number of rows and number of columns), and number of queries.

The next N lines contains M integer numbers 1 ≤ A_i,j ≤ 10⁴, the sizes of hives.

Afterward, Q lines (of two types) follow

First kind 1 I J P, 1 ≤ I ≤ N, 1 ≤ J ≤ M, 1 ≤ P ≤ 10⁴, the position of hive and the number of new-born bees.

Second kind 2 I₁ J₁ I₂ J₂, 1 ≤ I₁ ≤ I₂ ≤ N, 1 ≤ J₁ ≤ J₂ ≤ M, the boundaries of rectangular area for which you want to know the number of bees (more specifically the lower-left and upper right corners).

Output

For each query of second kind, output the number of bees.

Example Input

6 5 8
1 2 3 4 5
1 2 3 4 5
6 6 6 6 6
5 4 3 2 1
5 4 3 2 1
6 6 6 6 6
2 1 1 6 5
2 1 1 2 4
2 4 2 5 4
1 5 4 4
1 1 1 665
2 1 1 6 5
2 1 1 2 4
2 4 2 5 4

Example Output

120
20
18
789
685
22