问题描述

我们有一个 $H$ 行 $W$ 列的网格。第 $i$ 行和第 $j$ 列的区域将被称为网格 $(i,j)$。

从 $1$ 到 $h×w$ 的所有整数被写在整个网格中，写在网格 $(i,j)$ 中的整数是 $A_{i,j}$。

光头强以通过消耗 $|x-i|+|y-j|$ 点魔法，将放置在方格 $(i,j)$ 上的棋子传送到方格 $(x,y)$。

作为一个伐木工，他现在必须接受 Q 次技能测试。

第 $i$ 次测试将按以下方式进行:

最初，在写有整数 $L_i$ 的正方形上放置一个棋子。设 $x$ 是写在棋子所占的正方形中的整数。只要 $x$ 不是$R_i$，就反复将棋子移动到写有整数 $x+d$ 的方格。当 $X=R_i$ 时，测试结束。这里，保证 $R_i-l_i$ 是 $d$ 的倍数。

对于每个测试，找出在该测试期间消耗的魔法点的总和。

数据规模

$1≤H,W≤300$

$1≤D≤H×W$

$1≤A_{i,j}≤H×W$

$A_{ij}≠A_{x,y}((i,j)≠(x,y)$

$1≤Q≤10^5$

$1≤L_i≤R_i≤H×W$

$(R_i-l_i)$ 是 $D$ 的倍数。

输入

输入由标准输入按以下格式给出:

$H W D$

$A_{1,1}\ A_{1,2}...A_{1,w}$

$:$

$A_{H,1}\ A_{H,2} ...A_{H,W}$

$Q$

$L_1\ R_1$

$:$

$L_1\ R_1$

输出

对于每个测试，打印在该测试期间消耗的魔法点数的总和。

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

5

4写成正方形（1，2）。6写成正方形（3，3）。8写成正方形（3，1）。

因此，在第一次测试期间消耗的魔法点数的总和是（|3-1|+|3-2|）+（|3-3|+|1-3|）=5。

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

0
0

请注意，可能存在完全不移动工件的测试，并且可能存在多个相同的测试。

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

0
5
0