← 返回题目列表

AtCoder · abc089_d

D. 实践技能测试

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个网格 H 行和 W 列。广场位于 i第行和 j第列将被称为 Square (i,j).

的整数 1 通过 H×W 写在整个网格中,整数写在 Square 中 (i,j) is A_{i,j}.

你,一个魔法少女,可以传送放置在 Square 上的棋子 (i,j) 到广场 (x,y) 通过消费 |x-i|+|y-j| 魔法点。

你现在必须采取 Q 对你作为魔法少女能力的实际考验。

的 i第次测试将进行如下:

  • 最初,将一个棋子放置在整数所在的正方形上 L_i 。

  • 让 x 是写在该棋子所占据的方格中的整数。反复将棋子移动到整数所在的方格 写为 x+D ,只要 x 不是 R_i。测试结束时 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
  • 4 写在 Square 中 (1,2).

  • 6 写在 Square 中 (3,3).

  • 8 写在 Square 中 (3,1).

因此,第一次测试期间消耗的魔法点总和是 (|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