TopCoder

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

67.5% (27/40)

Tags

Description

在一塊方方正正的土地中,市長準備進行都市更新。這塊土地是 N×M 的矩形,左上角座標 (0,0),左下角座標 (N1,0),右上角座標 (0,M1),右下角座標 (N1,M1)。每一個座標 (i,j) 的位置都有一棟價值 aij 的建築物,一旦這個位置被都更,這棟建築就要被剷平。

市長想選一塊方正的矩形區域作為都更預定地,其中左上角為 (u,l),右下角為 (d,r),矩形兩軸平行都市邊界。他一共會提出 Q 種方案,想問你每種方案分別要剷除多少價值的建築物。

Input Format

輸入第一行是三個以空白分隔的整數 N,M,Q,分別代表都市的長寬和市長提出的方案數。

接下來有 N 行每行 M 個以空白分割的整數,其中第 i 行第 j 個數字表示 ai1,j1

接下來 Q 行,每行四個以空白分割的整數 u,l,d,r,代表市長提出的都更方案。

輸入保證 1N,M5001aij1091Q3000000ud<N0lr<M

Output Format

輸出 Q 行,每行包含一個整數,代表該筆詢問需要剷除建築的價值。

Sample Input 1

2 3 2
1 3 5
2 4 6
0 0 1 1
0 1 1 1

Sample Output 1

10
7

Sample Input 2

3 3 3
1 3 5
6 8 7
2 4 9
1 1 2 1
0 1 2 2
0 0 2 2

Sample Output 2

12
36
45

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2