Rectangle Sums

**Description:** Given an n x m grid and q queries (r1 c1 r2 c2), print the sum of the rectangle with top-left corner (r1, c1) and bottom-right corner (r2, c2), 1-based. **Input:** Line 1: n m q (1 <= n, m <= 1000, 1 <= q <= 10^5). Next n lines: m integers each (|a_ij| <= 10^9). Next q lines: r1 c1 r2 c2 (1 <= r1 <= r2 <= n, 1 <= c1 <= c2 <= m). **Output:** q lines — the rectangle sums. **Example:** 2 3 2 / 1 2 3 / 4 5 6 / 1 1 2 3 / 1 1 1 2 -> 21 / 3.