题目描述

$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$ の倍数であることは保証される。

それぞれの実技試験に対し、あなたの消費する魔力の総和を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$

输出格式

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

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

题目大意

• 给定一个 $h\times w$ 的矩阵，上面分别是 $1,2,...,h \times w$ 的每一个数。有 $Q$ 次询问，每次询问从数 $l$ 移动到数 $r$ 的代价。

• 每次移动的代价为两个数在矩阵上的曼哈顿距离。

• 移动方式为先从 $l$ 移动到 $l+d$，再移动到 $l+2\times d$ ... 直到移动到 $r$。其中 $d$ 是一开始给定的常数。保证 $r-l$ 是 $d$ 的倍数。

• $1 \le h,w\le 300,1 \le d \le h \times w,1 \le Q \le 10^5$

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

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

提示

制約

• $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$ の倍数

Sample Explanation 1

- $4$ が書かれたマスは、マス $(1,2)$ です。 - $6$ が書かれたマスは、マス $(3,3)$ です。 - $8$ が書かれたマスは、マス $(3,1)$ です。 よって、$1$ 回目の実技試験であなたの消費する魔力の総和は、$(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$ です。

Sample Explanation 2

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