Cho một bảng gồm m hàng và n cột.

Cho t yêu cầu có dạng a b c d, với mỗi yêu cầu, in ra tổng các số trong bảng chữ nhật con có hai góc đối diện là ô (a,b) và ô (c,d).

Input

Dòng đầu tiên chứa ba số nguyên dương m, n và t (1 ≤ m, n ≤ 200,1 ≤ t ≤ 40000).

Tiếp theo, mỗi dòng chứa n số nguyên là các phần tử của bảng.Các số này có trị tuyệt đối không quá ~ 10^9 ~.

Tiếp theo, mỗi dòng chứa bốn số nguyên a, b, c, d mô tả một yêu cầu (1 ≤ a ≤ c ≤ m, 1 ≤ b ≤ d ≤ n).

Output

Với mỗi yêu cầu, in ra tổng các số trong bảng chữ nhật con.

Sample

Input #1

2 1 3
-1
1
2 1 2 1
1 1 1 1
1 1 2 1
3 3 4
4 -5 -5
6 -6 -7
2 -6 4
3 2 3 3
2 3 2 3
3 2 3 3
1 2 2 3

Output #1

1
-1
0
-2
-7
-2
-23

Problem source: apok