AT_abc089_d [ABC089D] Practical Skill Test

有一个 $H$ 行 $W$ 列的格子，每个格子 $(i,j)$ 上写有一个整数 $A_{i,j}$，这些整数是 $1$ 到 $H \times W$ 的不重复整数。 你作为魔法少女，可以消耗魔力 $|x-i|+|y-j|$，将放在格子 $(i,j)$ 上的棋子瞬间移动到格子 $(x,y)$。 你需要进行 $Q$ 次实技考试，每次考试的流程如下： - 起始时，棋子放在写有整数 $L_i$ 的格子上。 - 记当前棋子所在格子上的整数为 $x$。只要 $x \neq R_i$，就将棋子移动到写有 $x+D$ 的格子上，重复此操作，直到 $x=R_i$ 时结束。 - 保证 $R_i-L_i$ 是 $D$ 的倍数。 请你计算每次实技考试中你消耗的魔力总和。

输入按以下格式从标准输入给出。 > $H$ $W$ $D$ > $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$ > $\vdots$ > $A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$ > $Q$ > $L_1$ $R_1$ > $\vdots$ > $L_Q$ $R_Q$

对于每次实技考试，输出你消耗的魔力总和。输出顺序与实技考试的顺序一致。

### 限制条件 - $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$ 的倍数 ### 样例解释 1 - 写有 $4$ 的格子是 $(1,2)$。 - 写有 $6$ 的格子是 $(3,3)$。 - 写有 $8$ 的格子是 $(3,1)$。 因此，第 $1$ 次实技考试你消耗的魔力总和为 $(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$。 ### 样例解释 2 请注意，可能存在完全不移动棋子的实技考试，或者多个实技考试内容相同。 由 ChatGPT 4.1 翻译