Bitaro’s Travel 2

The JOI Mountain Range consists of many mountains. It is represented as a grid with $H$ rows and $W$ columns, where the north-south direction is vertical, and the east-west direction is horizontal. The cell at the $i$-th row from the north ($1 ≤ i ≤ H$) and the $j$-th column from the west ($1 ≤ j ≤ W$) is denoted as $(i, j)$. There is exactly one mountain in each cell. The height of the mountain at cell $(i, j)$ is $T_{i, j}$.

Bitaro, the beaver, can move between the summits of the mountains using the procedure called high jump, which is described below. Here, $L$ is the parameter for his jumping skill.

1. Bitaro floats straight up from the summit of the current mountain. When the altitude of the summit is $x$, Bitaro will float up to the point of altitude $x + L + 0.5$.
2. Bitaro then repeats moving to the adjacent cell in one of the four directions without changing the altitude. The height of the mountains at the visiting cells must be lower than the altitude at which he is floating.
3. Bitaro finally lands at the summit of the current cell’s mountain.

Bitaro is planning for $Q$ trips. In the $k$-th trip ($1 ≤ k ≤ Q$), he plans to move from the summit of the cell $(A_k, B_k)$’s mountain to the summit of the cell $(C_k, D_k)$’s mountain by only using high jumps. He wants to know if these trips are possible, and if so, he also wants to know the minimum number of high jumps needed, because high jumps require much energy.

The information on the mountains, Bitaro’s jumping skill, and his trip plans, are given. Write a program that, for each trip plan, determines whether it is possible, and calculates the minimum number of high jumps needed if the trip is possible.

Read the following data from the standard input.

$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$

$A_Q$ $B_Q$ $C_Q$ $D_Q$

Write $Q$ lines to the standard output. In the $k$-th line ($1 ≤ k ≤ Q$), output the minimum number of high jumps needed in the $k$-th trip if the trip is possible. If the trip is impossible, output -1.

• $1 ≤ H$.
• $1 ≤ W$.
• $2 ≤ H \times W ≤ 300\, 000$.
• $1 ≤ L ≤ 10^9$.
• $1 ≤ T_{i, j} ≤ 10^9$ ($1 ≤ i ≤ H$, $1 ≤ j ≤ W$).
• $1 ≤ Q ≤ 300\, 000$.
• $1 ≤ A_k ≤ H$ ($1 ≤ k ≤ Q$).
• $1 ≤ B_k ≤ W$ ($1 ≤ k ≤ Q$).
• $1 ≤ C_k ≤ H$ ($1 ≤ k ≤ Q$).
• $1 ≤ D_k ≤ W$ ($1 ≤ k ≤ Q$).
• $(A_k, B_k) \ne (C_k, D_k)$ ($1 ≤ k ≤ Q$).
• Given values are all integers.