TopCoder

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

User's AC Ratio

96.7% (58/60)

Submission's AC Ratio

53.9% (139/258)

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

No. Testdata Range Score
1 0~3 20
2 4~7 20
3 8~11 20
4 12~15 20
5 16~19 20

Testdata and Limits

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