問題文

$M \times M$ マスの正方形 $A$ があります。 $A$ の各マスには値が設定されていて、マス $(i,j)$ の値は $A_{i,j}$ です。
ぽかーん懐古DPさんは、各 $(x_i,y_i)$ について、$A$ の中の空でない長方形の範囲のうち、マス $(x_i,y_i)$ を含み、その総和が $0$ になるものの個数を数えたいです。
ただし、ここで数えるのは長方形の範囲の取り出し方であることに注意してください。つまり、ある $2$ つの長方形の範囲に含まれる数が同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。

入力

$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$
• 入力はすべて整数

また、$N = 1300$ の evil ケースが存在する。このテストケースは提出結果には影響しない。

出力

各 $(x_i,y_i)$ について、$A$ の中の空でない長方形の範囲のうち、マス $(x_i,y_i)$ を含み、その総和が $0$ になるものの個数を出力してください。

サンプル

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