問題文

$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 \\leq H,W \\leq 300$
• $1 \\leq D \\leq H×W$
• $1 \\leq A_{i,j} \\leq H×W$
• $A_{i,j} \\neq A_{x,y} ((i,j) \\neq (x,y))$
• $1 \\leq Q \\leq 10^5$
• $1 \\leq L_i \\leq R_i \\leq 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_Q$ $R_Q$

出力

それぞれの実技試験に対し、あなたの消費する魔力の総和を出力せよ。

ただし、出力する順番は実技試験の行われる順とすること。

入力例 1

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

出力例 1

5

• $4$ が書かれたマスは、マス $(1,2)$ です。

• $6$ が書かれたマスは、マス $(3,3)$ です。

• $8$ が書かれたマスは、マス $(3,1)$ です。

よって、$1$ 回目の実技試験であなたの消費する魔力の総和は、$(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$ です。

入力例 2

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

出力例 2

0
0

駒を全く移動しない実技試験が存在する場合や、複数の実技試験の内容が同じ場合に注意してください。

入力例 3

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

出力例 3

0
5
0