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 _{i=c_1}^{c_2}\sum _{j=r_1}^{r_2}{a}_{i,j}={\displaystyle \sum _{\begin{array}{c}{c}_1\le i\le c_2\\ r_1\le j\le r_2\end{array}}{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\ast 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\mathrm{\%}$ số test có $m\ast n,q\le 1000$.

$30\mathrm{\%}$ số test có $1000<m\ast 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$.