题目背景

在远古遗迹阿卡纳姆的魔法领域中，存在一片被划分为 $H$ 行 $W$ 列的神秘区域，每个位置都由 $(i, j)$ 来唯一标识。这片区域承载着远古铭文，每个单元格内都刻有一个独特的数字，从 $1$ 到 $H \times W$，记作 $A_{i,j}$。

你身为一名空间术士，拥有驾驭魔力的能力，可以操控棋子进行瞬移。然而，每一次从 $(i, j)$ 移动至 $(x, y)$ 时，都会消耗等量的魔能，其计算方式如下：

在接下来的 $Q$ 次试炼中，你需要遵循固定规则，让棋子从指定位置出发，最终抵达目标位置。

试炼规则

初始状态：棋子最初放置在刻着数字 $L_i$ 的单元格。 传送律：

• 若棋子当前位于刻有编号 $x$ 的单元格，且 $x \neq R_i$，则你必须将棋子移动至刻有编号 $x+D$ 的单元格。
• 你需要重复执行此过程，直到棋子最终停留在刻有编号 $R_i$ 的单元格。
• 保证：对每次试炼，$R_i - L_i$ 一定是 $D$ 的整数倍，因此一定可以通过若干次跃迁从 $L_i$ 到达 $R_i$。

你的目标是计算并输出每次试炼所消耗的总魔能。

输入格式

第一行包含三个整数 $H, W, D$，分别表示：

• 魔法区域的行数 $H$，
• 魔法区域的列数 $W$，
• 跃迁步长 $D$。

接下来 $H$ 行，每行包含 $W$ 个整数，描述整个魔法区域的铭文编号，第 $i$ 行第 $j$ 列的编号为 $A_{i,j}$。

然后输入一个整数 $Q$，表示试炼的总次数。

接下来输入 $Q$ 行，每行包含两个整数 $L_i, R_i$，分别表示第 $i$ 次试炼的起始编号和目标编号。

输出格式

对于每次试炼，按照试炼进行的顺序，输出消耗的总魔能值。

样例

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

5

数据范围

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