Alice có một mảnh vườn hình chữ nhật \(n \times m\). Mỗi ô \((i,j)\) có \(a_{i,j}\) cây ăn quả. Alice muốn biết tổng số cây trong các hình chữ nhật con từ \((r_1,c_1)\) đến \((r_2,c_2)\).

Hãy trả lời \(q\) truy vấn nhanh chóng bằng prefix sum 2D.

Công thức: \(pref[i][j] = a[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]\)

Truy vấn: \(sum = pref[r_2][c_2] - pref[r_1-1][c_2] - pref[r_2][c_1-1] + pref[r_1-1][c_1-1]\)

Input

Dòng đầu chứa \(n, m, q\) (\(1 \le n, m \le 500\), \(1 \le q \le 10^5\)). \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số \(a_{i,j}\) (\(1 \le a_{i,j} \le 10^6\)). \(q\) dòng tiếp theo, mỗi dòng chứa \(r_1, c_1, r_2, c_2\).

Output

Với mỗi truy vấn, in ra tổng hình chữ nhật.

Example

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

Output:

12
28