An orchard is laid out as an R by C grid of plots; plot value g[i][j] is that plot's net yield (which may be negative for a plot running at a loss). Answer q queries. Each query gives r1 c1 r2 c2 (all 1-indexed, with r1 <= r2 and c1 <= c2) and asks for the total yield of the axis-aligned rectangle whose top-left plot is (r1, c1) and bottom-right plot is (r2, c2), inclusive.

Input format

Line 1: two integers R and C. Next R lines: each has C space-separated integers (one grid row). Next line: an integer q. Next q lines: four integers r1 c1 r2 c2.

Output format

Print q lines. Line i is a single integer: the rectangle sum for query i.

Constraints

• 1 <= R, C <= 300
• 1 <= q <= 100000
• -1000000 <= each plot value <= 1000000
• 1 <= r1 <= r2 <= R and 1 <= c1 <= c2 <= C

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

12
28

1 1
42
1
1 1 1 1

42