Cho một ma trận gồm ~m~ hàng và ~n~ cột. Cho ~t~ truy vấn có dạng x y p q, với mỗi truy vấn, in ra tổng các số trong ma trận chữ nhật con có hai góc đối diện là ô ~(x, y)~ và ô ~(p, q)~.

Input

Dòng đầu tiên chứa ba số nguyên dương ~m, n~ và ~t~ thỏa ~1 \le m, n \le 200; 1\le t \le 40000~.

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

~t~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x, y, p, q~ mô tả một truy vấn, dữ liệu thỏa ~1 \le x \le p \le m; 1 \le y \le q \le n~.

Output

Với mỗi truy vấn, in ra tổng các số trong ma trận chữ nhật con.

Samples

Sample Input 1

2 1 3
-1
1
2 1 2 1
1 1 1 1
1 1 2 1

Sample Output 1

1
-1
0

Sample Input 2

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

Sample Output 2

-2
-7
-2
-23