题目描述

我们有一个行数为 H ，列数为 W 的网格。并将1到 H×W这H*W个 整数写入网格中的方格，写在方格 (i,j) 中的整数是 Ai,j 。

魔法少女你可以通过消耗∣x−i∣+∣y−j∣ 点魔法值，将放置在方格(i,j) 的棋子传送到方格(x,y) 。

你现在需要参加 Q 次魔法少女能力的实际测试。

测试方法如下：

首先，在写有Li整数的方格上放置一枚棋子。

假设 x 是写在棋子所占位置上的整数。只要 x 不是 Ri ，就重复将棋子移动到写有整数 x+D 的位置。当 x=Ri出现时，测试结束。

这里可以保证 Ri−Li是 D 的倍数。

求每次测试消耗的魔点总和。

输入格式

第一行3个正整数H，W，D。

接下来H行，在这H行中，第i行第j个数为题目描述的Aij。

接下来是正整数Q，为测试的数量

接下来Q行，每行两个正整数Li和Ri，表示需要将棋子从Li传送到Ri。

输出格式

共Q行，每行一个整数，为将棋子从Li传送到Ri所需要花费的魔点值。

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

5

</p>

提示

一组测试，棋子需要从写有数字4的位置传送到写有数字8的位置。

4 所在位置为 (1,2) 。第一次传送到6，位置为（3，3），第二次传送到8，位置为（3，1）。

因此，第一次测试所消耗的魔法点数总和为

（∣3−1∣+∣3−2∣）+（∣3−3∣+∣1−3∣）=5 。

1≤H,W≤300

1≤D≤H×W

1≤Ai,j≤H×W

Ai,j≠Ax,y((i,j)≠(x,y))

1≤Q≤10⁵

1≤Li≤Ri≤H×W

(Ri−Li)能被D整除.

来源

2023-2024gcjs