题目描述

We have a grid with $H$ rows and $W$ columns. The square at the $i$-th row and the $j$-th column will be called Square $(i,j)$.

The integers from $1$ through $HW$ are written throughout the grid, and the integer written in Square $(i,j)$ is $A_{i,j}$.

You, a magical girl, can teleport a piece placed on Square $(i,j)$ to Square $(x,y)$ by consuming $|x-i|+|y-j|$ magic points.

You now have to take $Q$ practical tests of your ability as a magical girl.

The $i$-th test will be conducted as follows:

• Initially, a piece is placed on the square where the integer $L_i$ is written.

• Let $x$ be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer $x+D$ is written, as long as $x$ is not $R_i$. The test ends when $x=R_i$.

• Here, it is guaranteed that $R_i-L_i$ is a multiple of $D$.

For each test, find the sum of magic points consumed during that test.

我们有一个行数为 $H$ 列数为 $W$ 的网格。位于第 $i$ 行和第 $j$ 列的正方形将被称为正方形 $(i,j)$ 。

从 $1$ 到 $HW$ 的整数写满整个方格，写在方格 $(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$

输出格式

打印每次测试时消耗的魔法值总和。

输出应按照测试的顺序进行。

样例 #1

样例输入 #1

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

样例输出 #1

5

样例 #2

样例输入 #2

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

样例输出 #2

0
0

样例 #3

样例输入 #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

说明

数据规模与约定

• $1 \leq H,W \leq 300$
• $1 \leq D \leq HW$
• $1 \leq A_{i,j} \leq HW$
• $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 HW$
• $(R_i-L_i)$ 是 $D$ 的倍数。

样例 $1$ 解释

• $4$ 被写入方格 $(1,2)$ 。

• $6$ 写在 $(3,3)$ 方格中。

• $8$ 写在 $(3,1)$ 方格中。

因此，在第一次测试中消耗的魔法点数总和为 $(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$ 。

样例 $2$ 解释

请注意，可能有一次测试根本没有移动棋子，也可能有多次相同的测试。

样例 $3$ 解释