Submatrix Sum

You are given a 2D matrix of non-negative integers and a list of queries. Each query is specified by four indices \(x_1, y_1, x_2, y_2\) representing the top-left and bottom-right coordinates of a submatrix (using 0-indexing). Your task is to compute the sum of all elements within each specified submatrix.

Note: The indices satisfy \(0 \le x_1 \le x_2 < n\) and \(0 \le y_1 \le y_2 < m\), where \(n\) and \(m\) are the dimensions of the matrix.

inputFormat

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

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns in the matrix.
2. The next \(n\) lines each contain \(m\) space-separated integers representing the rows of the matrix.
3. The next line contains an integer \(q\) which denotes the number of queries.
4. The following \(q\) lines each contain four space-separated integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\) representing a query.

Indices are 0-indexed.

outputFormat

For each query, output a single integer which is the sum of the elements in the specified submatrix. Each answer must be printed on a new line to stdout.

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

12