Chocolate Sum Queries

You are given a two-dimensional grid of integers sized \(R \times C\). Your task is to answer several queries where each query asks for the sum of the elements inside a subgrid. A subgrid is defined by its top left corner \((r_1, c_1)\) and bottom right corner \((r_2, c_2)\). To answer the queries efficiently, you should preprocess the grid to construct a prefix sum array \(P\), where

[ P(i,j) = grid(i-1,j-1) + P(i-1,j) + P(i,j-1) - P(i-1,j-1), \quad 1 \leq i \leq R, ; 1 \leq j \leq C ]

When processing a query, use the precomputed prefix sums to compute the subgrid sum by:

[ \text{sum} = P(r_2,c_2) - P(r_1-1,c_2) - P(r_2,c_1-1) + P(r_1-1,c_1-1) ]

All indices are 1-indexed. Use standard input (stdin) and output (stdout) for reading input and writing output.

inputFormat

The first line contains two integers \(R\) and \(C\) (the number of rows and columns in the grid).

The next \(R\) lines each contain \(C\) integers, representing the grid.

The following line contains a single integer \(Q\) denoting the number of queries.

Each of the next \(Q\) lines contains four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\), representing a query asking for the sum of the subgrid from \( (r_1, c_1) \) to \( (r_2, c_2) \).

outputFormat

For each query, output the sum of the specified subgrid on a new line.

## sample

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

12
45

</p>