题目描述

给定一个 $h \times w$ 的矩阵，上面分别是 $1,2,...,h \times w$ 的每一个数。有 $Q$ 次询问，每次询问从数 $l$ 移动到数 $r$ 的代价。

每次移动的代价为两个数在矩阵上的曼哈顿距离。

移动方式为先从 $l$ 移动到 $l+d$，再移动到 $l+2\times d$ ... 直到移动到 $r$。其中 $d$ 是一开始给定的常数。保证 $r-l$ 是 $d$ 的倍数。

输入格式

第一行三个正整数 $h, w, d$，$1 \le h,w\le 300$，$1 \le d \le h \times w$。

接下来是一个 $h \times w$ 的矩阵。

接下来一个正整数 $Q$，$1 \le Q \le 10^5$。

接下来 $Q$ 行，每行 $2$ 个正整数 $l, r$。

输出格式

$Q$ 行，每行回答一个询问。

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

5

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

0
0

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

0
5
0