Cho ma trận nhị phân ~A~ gồm các số ~0~ và ~1~.

Có ~q~ truy vấn, mỗi truy vấn cho một hình chữ nhật ~(x_1,y_1,x_2,y_2)~.

Hãy cho biết trong hình chữ nhật đó có bao nhiêu ô chứa số ~1~.

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ố 0/1 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à số lượng số 1 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 0 1 1
0 1 0 1
1 1 1 0

1 2 3 4
2 2 3 4
1 1 3 3

Output

6
4
5