C - ビ太郎の旅 2 (Bitaro's Travel 2) Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点： 100 点

JOI 山脈にはたくさんの山が整列している． JOI 山脈は縦 H 行，横 W 列に区切られたマス目として表され， 縦方向は南北方向に平行であり，横方向は東西方向に平行である． 北から i 行目 (1 \leqq i \leqq H)，西から j 列目 (1\leqq j\leqq W) のマスのことをマス (i, j) と呼ぶ． 1 つのマスにはちょうど 1 つの山があり， マス (i, j) にある山の山頂の高さは T_{i, j} である．

ビ太郎のジャンプ力は L である．ビ太郎は山の山頂にいるとき， ハイジャンプ を行い，別の山の山頂に移動することができる． ハイジャンプ とは以下の操作を順に行うことを指す．

  • 今いる山の山頂から真上に飛び上がる．今いる山の山頂の高さが x であったとき，ビ太郎はそのマスの高さ x + L + 0.5 の位置に浮遊する．
  • 東西南北のいずれかに隣接するマスに高さを変えずに移動することを 0 回以上繰り返す．この際に訪れるすべてのマスについて，それらのマスにある山の山頂の高さは，ビ太郎が浮遊している高さより低くなければならない．
  • 今いるマスにある山の山頂に着地する．

ビ太郎は Q 回の旅を計画している． k 回目 (1\leqq k \leqq 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\leqq k \leqq Q) には， k 回目の旅を成功させるのに必要なハイジャンプの回数の最小値を出力せよ． ただし，旅が成功しない場合は，-1 を出力せよ．

制約

  • 1\leqq H．
  • 1\leqq W．
  • 2\leqq H\times W \leqq 300\,000．
  • 1\leqq L\leqq 10^{9}．
  • 1\leqq T_{i, j}\leqq 10^{9} (1\leqq i\leqq H,1\leqq j\leqq W)．
  • 1\leqq Q \leqq 300\,000．
  • 1\leqq A_{k} \leqq H (1\leqq k \leqq Q)．
  • 1\leqq B_{k} \leqq W (1\leqq k \leqq Q)．
  • 1\leqq C_{k} \leqq H (1\leqq k \leqq Q)．
  • 1\leqq D_{k} \leqq W (1\leqq k \leqq Q)．
  • (A_{k}, B_{k})\neq (C_{k}, D_{k}) (1\leqq k \leqq Q)．
  • 入力される値はすべて整数である．

小課題

  1. (10 点) H\times W \leqq 300，Q\leqq 150\,000．
  2. (20 点) H\times W \leqq 3\,000，Q\leqq 150\,000．
  3. (20 点) H\times W \leqq 150\,000，Q\leqq 150\,000，(A_{k}, B_{k}) = (1, 1) (1\leqq k \leqq Q)．
  4. (30 点) H\times W \leqq 150\,000，Q\leqq 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

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

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 の制約を満たす．