JOI 山脉上有许多山峰排列成行。JOI 山脉可以表示为一个被划分为 $H$ 行 $W$ 列的网格，纵向与南北方向平行，横向与东西方向平行。从北往南第 $i$ 行（$1 \leq i \leq H$），从西往东第 $j$ 列（$1\leq j\leq W$）的格子被称为格子 $(i, j)$。每个格子中正好有一个山峰，格子 $(i, j)$ 的山顶高度为 $T_{i, j}$。

比太郎的跳跃力为 $L$。比太郎在山顶时，可以通过高跳移动到另一个山顶。高跳是指顺序执行以下操作：

• 从当前位置山顶向上跳跃。若当前山顶高度为 $x$，比太郎将漂浮到高度 $x + L + 0.5$ 的位置。
• 可以任意次（包括 $0$ 次）以相同高度水平移动到东西南北相邻的格子。此移动过程中，经过的所有格子上的山顶高度都必须严格小于比太郎漂浮的高度。
• 在当前格子的山顶落地。

比太郎计划进行 $Q$ 次旅行。第 $k$ 次（$1\leq k\leq Q$）旅行的内容是：仅通过高跳，从格子 $(A_{k}, B_{k})$ 的山顶，移动到格子 $(C_{k}, D_{k})$ 的山顶。比太郎想知道每次旅行能否成功，如果成功，还想知道所需的高跳次数的最小值。

给定 JOI 山脉各山的高度、比太郎的跳跃力以及所有旅行计划，请你判断每次旅行是否可达，若可以还要输出所需高跳次数的最小值。

---

输入从标准输入按下列格式给出。

$H$ $W$ $L$ $T_{1,1}$ $T_{1,2}$ $\ldots$ $T_{1,W}$ $T_{2,1}$ $T_{2,2}$ $\ldots$ $T_{2,W}$ $\vdots$ $T_{H,1}$ $T_{H,2}$ $\ldots$ $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$），输出使得第 $k$ 次旅行成功所需的最小高跳次数。若该旅行无法成功，则输出 -1。

子任务

1.（$10$ 分）$H\times W \leq 300$，$Q\leq 150\,000$。
2.（$20$ 分）$H\times W \leq 3\,000$，$Q\leq 150\,000$。
3.（$20$ 分）$H\times W \leq 150\,000$，$Q\leq 150\,000$，$(A_{k}, B_{k}) = (1, 1)$（$1\leq k\leq Q$）。
4.（$30$ 分）$H\times W \leq 150\,000$，$Q\leq 150\,000$。
5.（$20$ 分）无额外约束。

---

样例解释 1

对于第 $1$ 次旅行，可以如下完成 $3$ 次高跳，从 $(1, 1)$ 的山顶到 $(2, 2)$ 的山顶。

• 第 $1$ 次高跳：
  • 从 $(1, 1)$ 山顶跳起，此时比太郎高度为 $6.5$。
  • 移动到 $(1, 2)$。$(1, 2)$ 山高度为 $3$，小于 $6.5$，可以通过。
  • 落地在 $(1, 2)$。
• 第 $2$ 次高跳：
  • 从 $(1, 2)$ 山顶跳起，比太郎高度为 $8.5$。
  • 移动到 $(1, 1)$。
  • 移动到 $(2, 1)$。
  • 落地在 $(2, 1)$。
• 第 $3$ 次高跳：
  • 从 $(2, 1)$ 山顶跳起，比太郎高度为 $13.5$。
  • 移动到 $(2, 2)$。
  • 落地在 $(2, 2)$。

不能用更少于 $3$ 次高跳完成第 $1$ 次旅行，因此第 $1$ 行输出 $3$。

第 $2$ 次旅行无法成功，因此第 $2$ 行输出 -1。

该输入满足所有子任务的约束。

---

样例解释 2

该输入满足所有子任务的约束。

---

样例解释 3

该输入满足子任务 $1,2,4,5$ 的约束。

数据范围与提示

• $1\leq H$。
• $1\leq W$。
• $2\leq H\times W\leq 300\,000$。
• $1\leq L\leq 10^{9}$。
• $1\leq T_{i, j}\leq 10^{9}$（$1\leq i\leq H, 1\leq j\leq W$）。
• $1\leq Q \leq 300\,000$。
• $1\leq A_{k} \leq H$（$1\leq k\leq Q$）。
• $1\leq B_{k} \leq W$（$1\leq k\leq Q$）。
• $1\leq C_{k} \leq H$（$1\leq k\leq Q$）。
• $1\leq D_{k} \leq W$（$1\leq k\leq Q$）。
• $(A_{k}, B_{k}) \neq (C_{k}, D_{k})$（$1\leq k\leq Q$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译