【codecomb2097】rect

2014年10月16日1,1060

Description

在一个n*m的格子棋盘上,有n*m堆石子,现在有两种操作:

1、给(x1,y1)->(x2,y2)这个矩形内所有的石子堆加入k个石子。1<=x1<=x2<=n,1<=y1<=y2<=m。

2、询问某格(x,y)上面有多少石子。

Input

第一行两个整数n和m,分别表示棋盘的长宽,n对应上述的x轴,m对应y轴。

第二行一个整数p,表示操作数量。

以下p行,首先一个是整数t,t=1或2,表示是哪种操作。 如果t=1,则后面跟5个整数x1,y1,x2,y2,k,如上所述。如果t=2,后面跟两个整数x,y,表示上述询问操作。

Output

对于每一个询问,输出石子数量。

Sample Input

3 3

2

1 1 1 2 2 1

2 1 1

 

Sample Output

 

1

 

Hint

 

数据范围:

 

40%的数据n,m<=1000

100%的数据n*m<1000000,p<=50000

答案保证在longint范围内

题解

二维树状数组。。