题目描述

我们有一个 $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

• 方格 $(1,2)$ 中写着 $4$。

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

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

因此，在第一次测试中消耗的魔法点的总和为 $(|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