分数: 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