题目背景

由于评测机性能差异，本题增加 1 秒时限。

题目描述

JOI 山脉由许多山峰组成，其地形被表示为一个 $H$ 行 $W$ 列的网格。其中：

• 南北方向为纵向，东西方向为横向；
• 位于北起第 $i$ 行（$1 \leq i \leq H$）、西起第 $j$ 列（$1 \leq j \leq W$）的单元格记为 $(i, j)$；
• 每个单元格中恰好有一座山峰，其高度为 $T_{i,j}$。

比太郎可以通过跳高（high jump）在山峰间移动，其跳跃技能参数为 $L$。具体步骤如下：

1. 上升阶段：从当前山峰上竖直上升。设当前山峰高度为 $x$，则 比太郎会上升到海拔 $x + L + 0.5$ 的位置。
2. 水平移动阶段：在保持海拔不变的前提下，重复向四个相邻方向（上下左右）移动。途经的所有单元格的山峰高度必须低于当前海拔。
3. 降落阶段：最终降落在目标单元格的山峰上。

比太郎计划进行 $Q$ 次旅行。在第 $k$ 次旅行（$1 \leq k \leq Q$）中，他希望仅通过跳高从起点 $(A_k, B_k)$ 移动到终点 $(C_k, D_k)$。需要解决的问题：

• 判断每次旅行是否可行。
• 若可行，计算所需的最少跳高次数；否则输出 $-1$。

输入格式

$H$ $W$ $L$
$T_{1,1}$ $T_{1,2}$ $\cdots$ $T_{1,W}$
$T_{2,1}$ $T_{2,2}$ $\cdots$ $T_{2,W}$
$\vdots$
$T_{H,1}$ $T_{H,2}$ $\cdots$ $T_{H,W}$
$Q$
$A_1$ $B_1$ $C_1$ $D_1$
$A_2$ $B_2$ $C_2$ $D_2$
$\vdots$
$A_Q$ $B_Q$ $C_Q$ $D_Q$

输出格式

输出 $Q$ 行。第 $k$ 行（$1 \leq k \leq Q$）输出：

• 若可行，输出最少跳高次数；
• 否则输出 $-1$。

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

3
-1
3
4
4
1

6 5 11
175 100 110 117 158
144 133 123 150 191
167 252 219 181 346
231 241 280 201 209
261 332 325 225 338
269 298 315 291 308
12
1 1 4 2
1 1 1 5
1 1 5 1
1 1 5 4
1 1 3 4
1 1 6 4
1 1 2 5
1 1 3 1
1 1 4 4
1 1 5 5
1 1 6 2
1 1 6 1

8
1
10
6
1
13
2
1
3
19
14
11

提示

样例解释

样例 $1$ 解释

对于第一次旅行，比太郎可以通过 $3$ 次跳高从单元格 $(1, 1)$ 的山峰移动到单元格 $(2, 2)$ 的山峰，具体步骤如下：

1. 第一次跳高
   • 从单元格 $(1, 1)$ 的山峰顶点浮升，此时海拔为 $6 + 2 + 0.5 = 8.5$（假设 $L=2$，原文未明确给出 $L$ 值，此处为推导）。
   • 移动到单元格 $(1, 2)$。由于该单元格山峰高度为 $3$，低于当前海拔 $8.5$，移动有效。
   • 降落在单元格 $(1, 2)$ 的山峰顶点。
2. 第二次跳高
   • 从单元格 $(1, 2)$ 的山峰顶点浮升，此时海拔为 $3 + 2 + 0.5 = 5.5$。
   • 移动到单元格 $(1, 1)$，再移动到单元格 $(2, 1)$。两处山峰高度均低于 $5.5$。
   • 降落在单元格 $(2, 1)$ 的山峰顶点。
3. 第三次跳高
   • 从单元格 $(2, 1)$ 的山峰顶点浮升，此时海拔为 $11 + 2 + 0.5 = 13.5$。
   • 移动到单元格 $(2, 2)$，山峰高度低于 $13.5$。
   • 降落在目标单元格 $(2, 2)$ 的山峰顶点。

无法以少于 $3$ 次跳高完成此次旅行，因此第一行输出 3。

对于第二次旅行，无法通过跳高到达目标，因此第二行输出 -1。

该样例满足所有子任务的限制。

样例 $2$ 解释

该样例满足所有子任务的限制。

数据范围

• $1 \leq H, W$；
• $2 \leq H \times W \leq 3\times 10^5$；
• $1 \leq L \leq 10^9$；
• $1 \leq T_{i,j} \leq 10^9$；
• $1 \leq Q \leq 3\times 10^5$；
• $1 \leq A_k,C_k\leq H$；$1\le B_k,D_k\le W$；
• $(A_k, B_k) \neq (C_k, D_k)$；
• 所有输入值为整数。

子任务

子任务	分数	$H\times W\le$	特殊性质
$1$	$10$	$300$
$2$	$20$	$3\times 10^3$
$3$		$150\,000$	$\text{A}$
$4$	$30$
$5$	$20$	无额外限制

特殊性质 $\text{A}$：$\forall 1\le i\le Q$，$(A_i,B_i)=(1,1)$。