Cho một hình chữ nhật có ~N~ hàng và ~M~ cột, các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~M~ từ trái sang phải. Mỗi ô (~i, j~) chứa một số nguyên ~A_{i,j}~.

Cho ~Q~ truy vấn, mỗi truy vấn gồm ~4~ số nguyên ~x_1, y_1, x_2, y_2~ mô tả một hình chữ nhật con có góc trái trên là ô (~x_1, y_1~) và góc phải dưới là ô (~x_2, y_2~). Với mỗi truy vấn, hãy in ra tổng của các số trong hình chữ nhật con đó.

Input

Dòng đầu tiên chứa ~3~ số nguyên ~N, M, Q~ (~1 \leq N, M \leq 1000; 1 \leq Q \leq 10^5~) — lần lượt là kích thước của hình chữ nhật và số truy vấn.

~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên, giá trị tuyệt đối của mỗi số không quá ~10^9~.

~Q~ dòng cuối cùng, mỗi dòng chứa ~4~ số nguyên ~x_1, y_1, x_2, y_2~ (~1 \leq x_1, x_2 \leq N; 1 \leq y_1, y_2 \leq M~) mô tả một hình chữ nhật cần truy vấn.

Output

Gồm ~Q~ dòng, mỗi dòng in tổng các số nằm trong hình chữ nhật tương ứng.

Scoring

Sample Input 1

4 5 3
-4 9 1 2 -3
3 2 3 -2 -4
7 -1 -1 2 1
5 3 -4 -8 2
2 3 2 5
2 1 4 5
1 1 2 2

Sample Output 1

-3
8
10

Sample Input 2

3 3 2
9 1 -4
2 -3 -3
-1 -2 5
2 2 3 3
3 1 3 2

Sample Output 2

-3
-3