Trong bảng \(m\)x\(n\) (\(m\) hàng, \(n\) cột), mỗi ô được ghi một số nguyên. Bạn hãy trả lời các truy vấn dạng \(r_1\:r_2\:c_1\:c_2\): tổng các số trong hình chữ nhật từ hàng \(r_1\) tới hàng \(r_2\), từ cột \(c_1\) tới cột \(c_2\). Nói cách khác với kí hiệu \(a_{i, j}\) là số được ghi tại dòng \(i\) cột \(j\) trong bảng, mỗi truy vấn dạng \(r_1\:r_2\:c_1\:c_2\) bạn cần tính giá trị biểu thức:

\[~\sum\limits_{i = c_1}^{c_2}\sum\limits_{j = r_1}^{r_2}a_{i,j} = \displaystyle\sum_{\substack{c_1 \le i \le c_2\\ r_1 \le j \le r_2}}a_{i,j}~\].

Đầu vào

Dòng đầu tiên chứa ba số tự nhiên \(m, n, q\) \((1 \le q, m*n \le 10^6)\), số hàng, số cột của bảng và số truy vấn.

\(m\) dòng tiếp theo mỗi dòng gồm \(n\) số nguyên có giá trị tuyệt đối không quá \(1000\) là các số ghi trên bảng.

\(q\) dòng tiếp theo mỗi dòng gồm bốn số tự nhiên \(r_1, r_2, c_1, c_2\) \((1 \le r_1 \le r_2 \le m, 1 \le c_1 \le c_2 \le n)\).

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Đầu ra

\(q\) dòng, mỗi dòng gồm duy nhất một số nguyên.

Subtask

\(30\%\) số test có \(m*n, q \le 1000\).

\(30\%\) số test có \(1000 < m*n \le 10^6, 1000 < q \le 10^4\).

Ví dụ

Đầu vào:

3 4 3
1 3 9 6
1 0 4 -8
4 8 2 8
1 1 1 1
2 2 2 3
2 3 2 4

Đầu ra:

1
4
14

Giải thích:

Trong truy vấn đầu tiên kết quả là \(a_{1, 1} = 1\).

Trong truy vấn tiếp theo kết quả là \(a_{2, 2} + a_{2, 3} = 0 + 4 = 4\).

Trong truy vấn thứ ba kết quả là \(a_{2, 3} + a_{2, 4} + a_{3, 2} + a_{3, 4} = 0 + 4 + (-8) + 8 + 2 + 8= 14\).