You are given an integer grid with R rows and C columns (1-indexed). Then you must answer Q queries. Each query gives the top-left corner (r1, c1) and bottom-right corner (r2, c2) of an axis-aligned rectangle, and asks for the sum of all grid values inside that rectangle, inclusive on all four sides. It is guaranteed that 1 ≤ r1 ≤ r2 ≤ R and 1 ≤ c1 ≤ c2 ≤ C for every query.

Input format

• Line 1: two integers R and C.
• The next R lines: each contains C space-separated integers — the grid, row by row.
• The next line: a single integer Q.
• The next Q lines: each contains four integers r1 c1 r2 c2 (1-indexed, inclusive).

Output format

Print Q lines. Line i is the sum of the submatrix requested by the i-th query.

Constraints

• 1 ≤ R, C ≤ 1000
• 1 ≤ Q ≤ 200000
• Each grid value is between -1000000 and 1000000.
• 1 ≤ r1 ≤ r2 ≤ R and 1 ≤ c1 ≤ c2 ≤ C.

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

14
38

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

-1
-10