577. 蝗灾

【题目描述】

C国国土辽阔，地大物博......但是最近却在闹蝗灾.....
我们可以把C国国土当成一个W×W的矩阵，你会收到一些诸如（X，Y，Z）的信息，代表（X，Y）这个点增多了Z只蝗虫，而由于C国政府机关比较臃肿，为了批复消灭蝗虫的请求需要询问一大堆的问题......每个询问形如（X1,Y1,X2,Y2），询问在（X1,Y1,X2,Y2）范围内有多少蝗虫（请注意询问不会改变区域内的蝗虫数），你作为一个C国的程序员，需要编一个程序快速的回答所有的询问。
NOTICE
C国一开始没有蝗虫。

【输入格式】

输入文件的第一行包括一个整数W，代表C国国土的大小。

第二行有一个整数N，表示事件数。

接下来有N行表示N个事件，以（1 X Y Z）的形式或（2,X1,Y1,X2,Y2）的形式给出，分别代表蝗虫的增加和询问。

【输出格式】

对于每个询问输出一个整数表示需要的结果。

【样例输入】

5
8
2 4 1 4 2
1 3 1 8
1 4 4 4
2 1 3 4 4
1 1 5 1
1 4 4 5
2 2 2 5 4
2 3 2 4 4

【样例输出】

0
4
9
9

【数据范围】

10%的数据满足W<=100,N<=100;

30%的数据满足W<=2000,N<=5000;

50%的数据满足W<=100000,N<=50000;

100%的数据满足W<=500000,N<=200000,每次蝗虫增加数不超过1000;