Matrix Prefix Sum Queries

Given an n x m matrix of integers, you are to answer q queries. Each query consists of two indices r and c (0-indexed) and asks for the sum of the submatrix that begins at the top-left corner (0, 0) and extends to the cell (r, c) inclusive. The answer to each query must be computed efficiently by utilizing the concept of prefix sums. In mathematical terms, for a query (r, c), you need to compute [ S(r,c)=\sum_{i=0}^{r}\sum_{j=0}^{c} A_{i,j} ] where (A_{i,j}) represents the element at row i and column j of the matrix.

For example, if the matrix is:

1 2 3 4 5 6 7 8 9

and the query is (1, 1), the answer is 1 + 2 + 4 + 5 = 12.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains two space-separated integers n and m, denoting the number of rows and columns of the matrix, respectively.

The following n lines each contain m space-separated integers representing the matrix.

The next line contains a single integer q, the number of queries.

This is followed by q lines, each containing two space-separated integers r and c (0-indexed), corresponding to a query asking for the sum of the submatrix from (0, 0) to (r, c).

outputFormat

The output should be written to standard output (stdout). For each query, output a single integer on a new line representing the sum of the submatrix from the top-left corner (0, 0) to the specified cell (r, c).## sample

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

1
12
45