JOI 山脉由许多山峰组成。它被表示为一个 $H$ 行 $W$ 列的网格，其中南北方向为垂直方向，东西方向为水平方向。从北边数第 $i$ 行（$1 \le i \le H$）和从西边数第 $j$ 列（$1 \le j \le W$）的单元格记为 $(i, j)$。每个单元格中恰好有一座山。单元格 $(i, j)$ 处山的高度为 $T_{i, j}$。

海狸 Bitaro 可以使用一种称为“高跳”的过程在山峰之间移动，该过程描述如下。这里，$L$ 是他跳跃技能的参数。

1. Bitaro 从当前山峰的峰顶垂直向上漂浮。当山峰的海拔为 $x$ 时，Bitaro 将漂浮到海拔为 $x + L + 0.5$ 的位置。
2. 随后，Bitaro 在保持海拔不变的情况下，重复移动到四个方向中相邻的单元格。所经过单元格的山峰高度必须低于他当前漂浮的海拔。
3. 最后，Bitaro 降落在当前单元格的山峰峰顶。

Bitaro 正在计划 $Q$ 次旅行。在第 $k$ 次旅行（$1 \le k \le Q$）中，他计划仅通过高跳从单元格 $(A_k, B_k)$ 的山峰移动到单元格 $(C_k, D_k)$ 的山峰。他想知道这些旅行是否可行，如果可行，他还想知道所需的最少高跳次数，因为高跳需要消耗大量能量。

给定山脉的信息、Bitaro 的跳跃技能以及他的旅行计划。请编写一个程序，对于每个旅行计划，判断其是否可行，并在可行时计算所需的最少高跳次数。

输入格式

从标准输入读取以下数据。

$H \ W \ L$ $T_{1,1} \ T_{1,2} \ \dots \ T_{1,W}$ $T_{2,1} \ T_{2,2} \ \dots \ T_{2,W}$ $\vdots$ $T_{H,1} \ T_{H,2} \ \dots \ 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 \le k \le Q$）中，如果第 $k$ 次旅行可行，输出所需的最少高跳次数。如果旅行不可行，则输出 -1。

数据范围

• $1 \le H$
• $1 \le W$
• $2 \le H \times W \le 300\,000$
• $1 \le L \le 10^9$
• $1 \le T_{i, j} \le 10^9$ ($1 \le i \le H, 1 \le j \le W$)
• $1 \le Q \le 300\,000$
• $1 \le A_k \le H$ ($1 \le k \le Q$)
• $1 \le B_k \le W$ ($1 \le k \le Q$)
• $1 \le C_k \le H$ ($1 \le k \le Q$)
• $1 \le D_k \le W$ ($1 \le k \le Q$)
• $(A_k, B_k) \neq (C_k, D_k)$ ($1 \le k \le Q$)
• 给定值均为整数。

子任务

1. (10 分) $H \times W \le 300, Q \le 150\,000$
2. (20 分) $H \times W \le 3\,000, Q \le 150\,000$
3. (20 分) $H \times W \le 150\,000, Q \le 150\,000, (A_k, B_k) = (1, 1)$ ($1 \le k \le Q$)
4. (30 分) $H \times W \le 150\,000, Q \le 150\,000$
5. (20 分) 无附加限制

样例

样例输入 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

样例输出 1

3
-1
3
4
4
1

说明

对于第一次旅行，Bitaro 可以通过 3 次高跳从单元格 $(1, 1)$ 的山峰移动到单元格 $(2, 2)$ 的山峰，方式如下：

• 第一次高跳
  • 从单元格 $(1, 1)$ 的山峰峰顶向上漂浮。此时他的海拔变为 6.5。
  • 移动到单元格 $(1, 2)$。这是可行的，因为单元格 $(1, 2)$ 的山峰高度为 3，低于 6.5。
  • 降落在单元格 $(1, 2)$ 的山峰峰顶。
• 第二次高跳
  • 从单元格 $(1, 2)$ 的山峰峰顶向上漂浮。此时他的海拔变为 8.5。
  • 移动到单元格 $(1, 1)$。
  • 移动到单元格 $(2, 1)$。
  • 降落在单元格 $(2, 1)$ 的山峰峰顶。
• 第三次高跳
  • 从单元格 $(2, 1)$ 的山峰峰顶向上漂浮。此时他的海拔变为 13.5。
  • 移动到单元格 $(2, 2)$。
  • 降落在单元格 $(2, 2)$ 的山峰峰顶。

以少于 3 次高跳结束第一次旅行是不可能的。因此，第一行输出 3。 对于第二次旅行，实现该旅行是不可能的。因此，第二行输出 -1。 该样例输入满足所有子任务的约束。

样例输入 2

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

样例输出 2

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

说明

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

样例输入 3

4 4 5
53 55 51 49
56 60 89 45
54 57 92 43
96 99 95 92
9
1 4 2 3
4 1 3 2
2 4 2 3
2 1 4 1
1 2 1 1
2 4 1 1
4 1 2 3
3 4 1 1
1 3 1 4

样例输出 3

-1
1
-1
-1
1
3
1
4
1

说明

该样例输入满足子任务 1、2、4 和 5 的约束。