Maximum Submatrix Sum from Fixed Top-left Corner

Sora has a magical data core consisting of an n \times m matrix of data blocks. Each block at position \((i,j)\) has a strength \(a_{i,j}\). Some blocks have negative strength due to hardware aging. To improve efficiency, Sora decides to select a block at \((x, y)\) as the upper-left corner of a new data core. Then, she cuts out a contiguous submatrix starting from \((x, y)\), and she wants to maximize the total computational power (i.e. the sum of strengths) of the selected submatrix.

You are given \(Q\) queries. Each query provides a position \((x, y)\). For each query, determine the maximum total computational power obtainable from any submatrix whose top-left corner is \((x, y)\). The sum for a submatrix defined by top-left \((x,y)\) and bottom-right \((p,q)\) is given by:

[ \text{sum}(x,y,p,q)=\sum_{i=x}^{p}\sum_{j=y}^{q}a_{i,j} ]

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the matrix.

Each of the next \(n\) lines contains \(m\) integers, where the \(j\)-th integer of the \(i\)-th line represents \(a_{i,j}\).

The next line contains an integer \(Q\), the number of queries. Each of the following \(Q\) lines contains two integers \(x\) and \(y\), representing the top-left coordinates for the new data core.

outputFormat

For each query, output a single line containing one integer: the maximum computational power (i.e. the maximum sum over all submatrices starting at \((x, y)\)).

sample

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

9
5
9