配点 : $400$ 点

問題文

$H$ 行 $W$ 列のマス目があり、$i$ 行目の $j$ 列目のマスをマス $(i,j)$ と呼びます。

このマス目には $1$ から $H \times 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 \times W$
• $1 \leq A_{i,j} \leq H \times 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 \times 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$

出力

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

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

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)$ です。

よって、$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