TopCoder

Thumb 273182be425dbb6f
AWfulsome
It's so $\huge{AW^{fulsome}}$

User's AC Ratio

98.0% (49/50)

Submission's AC Ratio

57.1% (116/203)

Description

你,もも,在跟醬油玩堆石子遊戲....

這個遊戲是在一個n×n的棋盤上玩的。

玩法是這樣:

醬油(莊家)每次有兩種操作
1. 在(x,y)那一格上面多放z顆石子
2. 問你(x_1 ,y_1 )到(x_2 ,y_2 )這個矩形區域總共有多少石頭。
全部答對了你就可以欣賞醬油的收藏。

但是因為棋盤太大了,所以你決定寫個程式來幫助你。

Input Format

第1行有1個數字n,代表棋盤大小。
接下來有多筆操作,請讀到EOF為止。

每筆操作的格式是這樣
第一種操作 : 1 x y z (0≤x,y<n,−32768≤z≤32767)
第二種操作 : 2 x1 y1 x2 y2(0≤x1≤x2<n,0≤y1≤y2<n)

Output Format

對於每個第二種操作輸出一行答案。

Sample Input

4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3

Sample Output

3
4

Hints

14%的測資滿足n≤300,詢問數≤30000
100%的測資滿足n≤1024,詢問數≤65000

Problem Source

Step5

Subtasks

For Testdata: 0 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 20
For Testdata: 8 ~ 11, Score: 20
For Testdata: 12 ~ 15, Score: 20
For Testdata: 16 ~ 19, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144
16 1000 65536 262144
17 1000 65536 262144
18 1000 65536 262144
19 1000 65536 262144