Cho ma trận ~A~ kích thước ~n\times m~. Có ~q~ truy vấn, mỗi truy vấn gồm bốn số ~x_1,y_1,x_2,y_2~.

Hãy tính tổng các phần tử nằm trong hình chữ nhật có góc trên trái ~(x_1,y_1)~ và góc dưới phải ~(x_2,y_2)~.

Dữ liệu vào:

• Dòng đầu gồm chứa 3 số nguyên dương n, m, q;
• n dòng tiếp theo, mỗi dòng chứa m số của ma trận;
• q dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương ~x_1,y_1,x_2,y_2~.

  Kết quả

Ghi ra q dòng, mỗi dòng là 1 số là tổng của một hình chữ nhật con.

Ràng buộc:

• ~1\le n,m\le1000~
• ~1\le q\le10^5~
• ~|A[i][j]|\le10^6~

Ví dụ

Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1 1 2 2
2 2 3 4
1 3 3 3

Output

14
54
21