Problem Statement

There is a square $A$ of $M \times M$ cells. Each cell of $A$ has a value, and the value of cell $(i,j)$ is $A_{i,j}$.
For each $(x_i,y_i)$, Pokan Kaiko DP wants to count the non-empty rectangular regions in $A$ that contain cell $(x_i,y_i)$ and whose sum is $0$.
Note that what is counted here is the ways of choosing a rectangular region. That is, even if $2$ rectangular regions contain the same numbers, they are counted separately if their positions differ.

Input

$N\ M$
$A_{1,1} \cdots A_{1,M}$
$\hspace{6pt}\vdots$
$A_{M,1} \cdots A_{M,M}$
$x_1\ \ y_1$
$\hspace{3pt}\vdots$
$x_N\ \ y_N$

• $1≤N≤10$
• $1≤M≤130$
• $-10^9≤A_{i,j}≤10^9$
• $1≤x_i,y_i≤M$
• All input values are integers.

In addition, there is an evil case with $N = 1300$. This test case does not affect the submission result.

Output

For each $(x_i,y_i)$, output the number of non-empty rectangular regions in $A$ that contain cell $(x_i,y_i)$ and whose sum is $0$.

Sample

4 4
0 -1 5 5
-3 3 0 -3
5 -1 -5 4
-4 4 -5 0
2 4
4 1
4 3
2 2

2
1
1
5