Grid Queries for Coin Collection

You are given a grid with n rows and m columns. Each cell in the grid contains a certain number of coins. You need to answer q queries. Each query specifies a subrectangle of the grid by its top-left corner (x₁, y₁) and bottom-right corner (x₂, y₂). For every query, compute the total number of coins inside the corresponding subrectangle.

A common approach to answer these queries efficiently is to use a prefix sum matrix. The prefix sum is computed using the following formula in \(\LaTeX\):

[ P(i,j)=\text{grid}(i,j)+P(i-1,j)+P(i,j-1)-P(i-1,j-1) ]

All indices are 1-indexed.

inputFormat

The first line contains two integers n and m representing the number of rows and columns respectively.

The next n lines each contain m integers representing the grid values.

The following line contains an integer q, the number of queries.

Each of the next q lines contains four integers: x₁ y₁ x₂ y₂, which specify the top-left and bottom-right coordinates of the query subrectangle.

outputFormat

For each query, output a single line containing the sum of coins in the specified subrectangle.

## sample

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
1 1 2 2
2 2 3 4

14
54

</p>