Prefix Sum Grid Queries

You are given an \(n \times n\) grid of integers. Your task is to answer \(q\) queries about the sums of various subgrids. For each query, you are provided with four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) that represent the coordinates of the top-left and bottom-right corners of the subgrid (using 1-indexing).

To solve the problem efficiently, you are required to precompute a prefix sum array \(P\) based on the original grid \(A\) using the following formula:

[ P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] ]

After computing \(P\), any query can be answered in \(O(1)\) time using:

[ \text{sum} = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1] ]

Read the input from stdin and output the answer for each query on a new line to stdout.

inputFormat

The input is given in the following format:

• The first line contains an integer (n), representing the size of the grid.
• The next (n) lines each contain (n) space-separated integers, representing the rows of the grid.
• The next line contains an integer (q), the number of queries.
• The following (q) lines each contain four space-separated integers: (x_1), (y_1), (x_2), (y_2), defining a query for the subgrid sum.

Note: The grid uses 1-indexing.

outputFormat

For each query, print a single integer on a separate line, which is the sum of the subgrid defined by the given coordinates.## sample

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

12
45