ADABEHIVE - Ada and Behives

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 ≤ 105, 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 ≤ Ai,j ≤ 104, 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 ≤ 104, the position of hive and the number of new-born bees.

Second kind 2 I1 J1 I2 J2, 1 ≤ I1 ≤ I2 ≤ N, 1 ≤ J1 ≤ J2 ≤ 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

Added by:Morass
Date:2017-02-11
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-04-15 14:38:42
@jmr99
@harsh_03
Answer can exceed 32-bit
2018-07-17 14:16:20
@[Rampage] Blue.Mary pls help
i have solved the MATSUM problem but not getting the correct answer for this question pls help!!
i am using BIT.

Last edit: 2018-07-17 14:17:32
2017-12-12 14:25:18
I am getting WA but example case is working
2017-02-12 02:41:07
@[Rampage] Blue.Mary: Thanks!
2017-02-12 02:40:40 [Rampage] Blue.Mary
It seems this can be put into "basics" section.
2017-02-12 02:35:40
@[Rampage] Blue.Mary: Oh :'( hmm thanks (do you have any advises for it? I don't want to remove it completely, since It took a while to prepare it, yet I see it is not good to keep duplicates )
2017-02-12 02:28:17 [Rampage] Blue.Mary
This is almost the same as: http://www.spoj.com/problems/MATSUM/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.