2D Prefix Sum Queries

In this problem, you are given a two-dimensional grid of integers with dimensions (n \times m). Your task is to answer several queries where each query asks for the sum of elements in the subgrid defined by the upper-left corner ((x_1, y_1)) and the lower-right corner ((x_2, y_2)).

The key idea is to precompute a 2D prefix sum array (P) where each element is defined by the recurrence:
$$ P[i,j] = A[i,j] + P[i-1,j] + P[i,j-1] - P[i-1,j-1]

$$
This allows you to answer each query in constant time using the formula:
$$

\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]

$$

The input is read from standard input (stdin) and the answers should be printed to standard output (stdout). ## inputFormat The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns respectively. The next \(n\) lines each contain \(m\) integers representing the grid. The subsequent line contains a single integer \(q\) representing the number of queries. Each of the following \(q\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\) which describe a query. ## outputFormat For each query, output a single line containing the sum of the specified subgrid.## sample

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

12
33

$$