Cho một hình chữ nhật \(m \cdot 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ố \(x_1, y_1, x_2, y_2\) (\(x_1 \le x_2, y_1 \le y_2\)). Hãy tính tổng các số trong hình chữ nhật có góc trên trái là \((x_1, y_1)\) và góc dưới phải là \((x_2, y_2)\). 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 \le m, n \le 1000, 1 \le q \le 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 \(\le 10^9\).
• \(q\) dòng tiếp theo, mỗi dòng chứa 4 số \(x_1, y_1, x_2, y_2\) (\(1 \le x_1 \le x_2 \le m, 1 \le y_1 \le y_2 \le n\)).

Output

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

Example

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

39
11
4