Cho một hình chữ nhật có \(N\) hàng và \(M\) cột có số thứ tự được đánh từ trên xuống và từ trái sang phải.

Trên mỗi ô có viết một số nguyên và nhiệm vụ chúng ta phải trả lời \(Q\) truy vấn. Mỗi truy vấn sẽ gồm bốn số nguyên là \(x_1, y_1, x_2, y_2\), sẽ mô tả một khu vực con trong hình chữ nhật. Ứng với mỗi truy vấn, hãy in ra tổng của của khu vực con đó, có điểm \((x_1, y_1)\) là ô góc trái trên và có điểm \((x_2, y_2)\) là ô ở góc phải dưới của khu vực.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) (chiều rộng) và \(M\) (chiều dài) \((1 \leq N, M \leq 1000)\)
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên, giá trị tuyệt đối của mỗi số nguyên này không vượt quá \(10^9\)
• Dòng kế tiếp, chứa một số nguyên \(Q\) (số truy vấn) \((1 \leq Q \leq 10^5)\)
• \(Q\) dòng kết tiếp, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\). \((1 \leq x_1 \leq x_2 \leq N)\), \((1 \leq y_1 \leq y_2 \leq M)\)

Output

• In ra \(Q\) dòng, ứng với truy vấn thứ \(i\), in ra một số nguyên là tổng của khu vực hình chữ nhật được nhắc đến bởi truy vấn thứ \(i\).

Example

Test 1

Input

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

Output

-9
3
-6
6

Note