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