2D Rectangle Sum Query Using Prefix Sums

You are given a 2D array A of size n × m and q rectangle queries. Each query is represented by four integers \(x_1, y_1, x_2, y_2\) (using 1-indexing), indicating the top-left and bottom-right corners of the rectangle. Your task is to compute the sum of all elements inside each queried rectangle.

One efficient way to handle multiple queries is by using a prefix sum matrix. Construct a prefix sum matrix \(PS\) defined as

[ PS[i][j] = \sum_{k=1}^{i}\sum_{l=1}^{j} A_{k,l}, \quad 1 \leq i \leq n, ; 1 \leq j \leq m. ]

Then the sum \(S\) for a rectangle defined by \((x_1, y_1)\) and \((x_2, y_2)\) can be computed in \(O(1)\) time as:

[ S = PS[x_2][y_2] - PS[x_1-1][y_2] - PS[x_2][y_1-1] + PS[x_1-1][y_1-1]. ]

If there are no queries, simply output nothing. The input is read from stdin and output to stdout.

inputFormat

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

• The first line contains two integers n and m, the number of rows and columns of the matrix.
• The next n lines each contain m space-separated integers representing the matrix A.
• The following line contains an integer q, the number of queries.
• The next q lines each contain four integers x₁ y₁ x₂ y₂ representing a query.

outputFormat

For each query, output the computed rectangle sum on a separate line to stdout.

## sample

3 3
2 1 4
3 0 5
7 2 2
1
1 1 2 2

6