Cho một hình chữ nhật m*n gồm m hàng và n cột. Các hàng và cột được đánh thứ tự tăng dần từ trái sang phải, từ trên xuống dưới (bắt đầu bằng 1).

Cho q truy vấn: mỗi truy vấn gồm 4 số x1, y1, x2, y2 (x1 <= x2, y1 <= y2). Hãy tính tổng các số trong hình chữ nhật có góc trên trái là (x1, y1) và góc dưới phải là (x2, y2). Ký hiệu (x, y) nghĩa là ô ở hàng x cột y.

Input:

Dòng đầu chứa 3 số nguyên dương m, n, q (1 <= m, n <= 1000, 1 <= q <= 10^5).

m dòng tiếp theo, mỗi dòng chứa n số là các số trong bảng với giá trị tuyệt đối <= 10^9

q dòng tiếp theo, mỗi dòng chứa 4 số x1, y1, x2, y2 (1 <= x1 <= x2 <= m, 1 <= y1 <= y2 <= n)

Output:

In ra q dòng, mỗi dòng chứa đáp số của truy vấn tương ứng

Ví dụ:

Input:

3 4 3

1 2 3 4

-1 -2 0 5

9 9 4 5

1 1 3 4

2 2 3 3

1 4 1 4

Output:

39

11

4