方格跳跃
题号：NC20907
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

给定一个网格图，每个格子上都有一个数，初始在编号为 L 的格子上，下一次需要走到格子上的数为 (x+d) 的格子上，代价为两个格子之间的曼哈顿距离（坐标为(xi,yi)与坐标为(x_j,y_j)的两个点之间的曼哈顿距离为(|xi-xj|+|yi-yj|)）。 问要走到格子上的数为 R 的格子至少需要花费多少代价。
多组测试数据。

输入描述:

第一行三个整数 H,W,d，表示网格图的长度与宽度，d 的含义如题面所示。
接下来 W 行，每行 H 个整数表示网格图中每个格子的数。
下一行是一个整数 Q(1≤ Q≤105)，表示询问组数。
接下来 Q 行，每行两个整数 L 和 R 代表一组询问。
保证数据合法，即不存在无法从 L 按题意跳若干步跳到 R 的数据。

输出描述:

输出包含 Q 行，每行为一个整数 k，表示每一组测试数据需要花费的代价。
输出应该按照输入的顺序。
示例1

输入

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

输出

复制 
5

说明

样例仅一组测试数据。
最初在位置(1,2)，格子上的数为4，然后直接传送到格子上的数为6的格子，即位置(3,3)，然后传送到格子(3,1)上，格子上的数为8，等于Ri了。
因此，消耗的代价为(|3-1|+|3-2|)+(|3-3|+|1-3|)=5。
数据保证0\le H,W\le 2000,\, 0\le D\le H\times W.