Treasure Grid Queries

You are given a grid with n rows and m columns. Each cell in the grid contains a tuple of two integers: the amount of gold and the number of items. You are also given q queries. Each query is defined by four integers r1, c1, r2, and c2 where (r1, c1) is the top‐left and (r2, c2) is the bottom‐right coordinate of a sub-grid. For each query, compute the sum of gold and the sum of items in the specified sub-grid.

The solution should efficiently process multiple queries. A common approach is to use 2D prefix sum arrays. The prefix sum arrays for gold and items can be computed as follows:

\[ \text{prefix}[i][j] = \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] + \text{value}_{i,j} \]

Using this method, each query can be answered in constant time.

inputFormat

The first line contains three integers n, m, and q representing the number of rows, columns, and queries respectively. This is followed by n lines, each containing 2*m integers. Each line lists the gold and item values for each cell in that row (first the gold value then the item value for each cell). After the grid, there are q lines, each containing four integers r1, c1, r2, and c2 describing a query.

Note: The grid uses 1-indexed coordinates.

outputFormat

For each query, output a line with two integers: the sum of gold and the sum of items in the sub-grid defined by that query.

## sample

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

12 11
28 12

</p>