AT_abc394_g [ABC394G] Dense Buildings

東西南北方向に $ H\times W $ 個の区画に区切られた街があり、各区画にはちょうど $ 1 $ つのビルが立っています。 具体的には北から $ i $ 番目 $ (1\leq i\leq H) $ かつ西から $ j $ 番目 $ (1\leq j\leq W) $ の区画（以下、区画 $ (i,j) $ とよぶ）には $ F_{i,j} $ 階建てのビルがあります。 高橋君には $ 2 $ 種類の移動方法があり、区画 $ (i,j) $ のビルの $ X $ 階 $ (1\leq X\leq F_{i,j}) $ にいるとき、そこから次のような移動が可能です。 - 同じビルの中の $ 1 $ つ上の階または $ 1 $ つ下の階へ **階段** を使って移動する。ただし、 $ 1 $ 階から $ 1 $ つ下の階への移動および、 $ F_{i,j} $ 階から $ 1 $ つ上の階への移動はできない。 - 東西南北に隣接する区画にあるビルのうち、 $ X $ 階建て以上であるものを $ 1 $ つを選び、そのビルの $ X $ 階へ **（上空）通路** を使って移動する。 ただし、区画 $ (i,j) $ と区画 $ (i',j') $ が東西南北に隣接するとは、 $ \lvert i-i'\rvert+\lvert j-j'\rvert=1 $ であることをさします。 $ Q $ 個の質問が与えられるので、それぞれの質問に答えてください。 $ i $ 個目 $ (1\leq i\leq Q) $ の質問は次のようなものです。 > 区画 $ (A_i,B_i) $ にあるビルの $ Y_i $ 階から、区画 $ (C_i,D_i) $ にあるビルの $ Z_i $ 階へ高橋君が移動する時に、 **階段** を使う回数としてあり得る最小の値を求めよ。 > ここで、階段を使う回数は $ 1 $ つ上の階または $ 1 $ つ下の階へ移動するたびにカウントされ、同じビルの中でも重複してカウントされるものとする。 (例えば、あるビルを $ 1 $ 階から $ 6 $ 階まで移動したとき、 $ 5 $ 回階段を使用したと数える。) > また、通路の使用回数を最小とする必要はないことに注意せよ。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ F_{1,1} $ $ F_{1,2} $ $ \ldots $ $ F_{1,W} $ $ F_{2,1} $ $ F_{2,2} $ $ \ldots $ $ F_{2,W} $ $ \vdots $ $ F_{H,1} $ $ F_{H,2} $ $ \ldots $ $ F_{H,W} $ $ Q $ $ A_1 $ $ B_1 $ $ Y_1 $ $ C_1 $ $ D_1 $ $ Z_1 $ $ A_2 $ $ B_2 $ $ Y_2 $ $ C_2 $ $ D_2 $ $ Z_2 $ $ \vdots $ $ A_Q $ $ B_Q $ $ Y_Q $ $ C_Q $ $ D_Q $ $ Z_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目の質問に対する答えを整数で出力せよ。

### Sample Explanation 1 $ 1 $ 番目の質問について、例えば以下のように移動すると階段を合計で $ 10 $ 回使用して、 区画 $ (1,1) $ のビルの $ 10 $ 階から区画 $ (3,1) $ のビルの $ 6 $ 階へ移動することができます。 - 通路を使って、区画 $ (1,1) $ のビルの $ 10 $ 階から区画 $ (1,2) $ のビルの $ 10 $ 階へ移動する。 - 階段を $ 4 $ 回使って、区画 $ (1,2) $ のビルの $ 10 $ 階から $ 6 $ 階へ移動する。 - 通路を使って、区画 $ (1,2) $ のビルの $ 6 $ 階から区画 $ (1,3) $ のビルの $ 6 $ 階へ移動する。 - 階段を $ 3 $ 回使って、区画 $ (1,3) $ のビルの $ 6 $ 階から $ 3 $ 階へ移動する。 - 通路を使って、区画 $ (1,3) $ のビルの $ 3 $ 階から区画 $ (2,3) $ のビルの $ 3 $ 階へ移動する。 - 通路を使って、区画 $ (2,3) $ のビルの $ 3 $ 階から区画 $ (3,3) $ のビルの $ 3 $ 階へ移動する。 - 階段を $ 3 $ 回使って、区画 $ (3,3) $ のビルの $ 3 $ 階から $ 6 $ 階へ移動する。 - 通路を使って、区画 $ (3,3) $ のビルの $ 6 $ 階から区画 $ (3,2) $ のビルの $ 6 $ 階へ移動する。 - 通路を使って、区画 $ (3,2) $ のビルの $ 6 $ 階から区画 $ (3,1) $ のビルの $ 6 $ 階へ移動する。 階段の使用回数が $ 9 $ 回以下となるように、区画 $ (1,1) $ のビルの $ 10 $ 階から区画 $ (3,1) $ のビルの $ 6 $ 階へ移動することはできないため、 $ 10 $ を出力します。 $ 2 $ 番目の質問については、区画 $ (1,2) $ のビルへ通路を用いて移動した後に、階段を $ 2 $ 回用いて $ 6 $ 階から $ 4 $ 階へ下りると、階段を $ 2 $ 回使用することで、区画 $ (1,1) $ のビルの $ 6 $ 階から区画 $ (1,2) $ のビルの $ 4 $ 階へ移動することができます。 ### Constraints - $ 1\leq H \leq 500 $ - $ 1\leq W \leq 500 $ - $ 1\leq F_{i,j} \leq 10^6 $ - $ 1\leq Q\leq 2\times 10^5 $ - $ 1\leq A_i,C_i\leq H $ - $ 1\leq B_i,D_i\leq W $ - $ 1\leq Y_i\leq F_{A_i,B_i} $ - $ 1\leq Z_i\leq F_{C_i,D_i} $ - $ (A_i,B_i,Y_i)\neq (C_i,D_i,Z_i) $ - 入力はすべて整数