AT_abc365_f [ABC365F] Takahashi on Grid

[problemUrl]: https://atcoder.jp/contests/abc365/tasks/abc365_f 平面上に無限個のマスがあります。 整数の $ 2 $ つ組 $ (x,y) $ すべてに対して対応するマスがひとつ存在し、マス $ (x,y) $ と呼ぶことにします。 すべてのマスは、それぞれ空きマスか壁マスのどちらか一方です。 長さ $ N $ の正整数列 $ L=(L\ _\ 1,L\ _\ 2,\dotsc,L\ _\ N),U=(U\ _\ 1,U\ _\ 2,\dotsc,U\ _\ N) $ が与えられます。 ここで、$ i=1,2,\ldots,N $ について $ L\ _\ i,U\ _\ i $ は $ 1\leq\ L\ _\ i\leq\ U\ _\ i\leq10\ ^\ 9 $ を満たします。 マス $ (x,y)\ (1\leq\ x\leq\ N,L\ _\ x\leq\ y\leq\ U\ _\ x) $ はすべて空きマスで、それ以外のマスは壁マスです。 高橋くんが空きマスであるマス $ (x,y) $ にいるとき、次の行動のいずれかを行うことができます。 - マス $ (x+1,y) $ が空きマスならば、マス $ (x+1,y) $ に移動する。 - マス $ (x-1,y) $ が空きマスならば、マス $ (x-1,y) $ に移動する。 - マス $ (x,y+1) $ が空きマスならば、マス $ (x,y+1) $ に移動する。 - マス $ (x,y-1) $ が空きマスならば、マス $ (x,y-1) $ に移動する。 どの空きマスどうしも、高橋くんが行動を繰り返すことで行き来できることが保証されます。 次の形式の $ Q $ 個の質問に答えてください。 $ i $ 番目 $ (1\leq\ i\leq\ Q) $ の質問では整数の $ 4 $ つ組 $ (s\ _\ {x,i},s\ _\ {y,i},t\ _\ {x,i},t\ _\ {y,i}) $ が与えられるので、高橋くんがマス $ (s\ _\ {x,i},s\ _\ {y,i}) $ にいるところからマス $ (t\ _\ {x,i},t\ _\ {y,i}) $ に移動するために必要な行動回数の最小値を求めてください。 各質問について、与えられる $ 2 $ つのマスは空きマスであることが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L\ _\ 1 $ $ U\ _\ 1 $ $ L\ _\ 2 $ $ U\ _\ 2 $ $ \vdots $ $ L\ _\ N $ $ U\ _\ N $ $ Q $ $ s\ _\ {x,1} $ $ s\ _\ {y,1} $ $ t\ _\ {x,1} $ $ t\ _\ {y,1} $ $ s\ _\ {x,2} $ $ s\ _\ {y,2} $ $ t\ _\ {x,2} $ $ t\ _\ {y,2} $ $ \vdots $ $ s\ _\ {x,Q} $ $ s\ _\ {y,Q} $ $ t\ _\ {x,Q} $ $ t\ _\ {y,Q} $

$ Q $ 行にわたって出力せよ。 $ i $ 行目 $ (1\leq\ i\leq\ Q) $ には、$ i $ 番目の質問に対する答えを出力せよ。

### 制約 - $ 1\leq\ N\leq2\times10\ ^\ 5 $ - $ 1\leq\ L\ _\ i\leq\ U\ _\ i\leq10\ ^\ 9\ (1\leq\ i\leq\ N) $ - $ \lbrack\ L\ _\ i,U\ _\ i\rbrack\cap\lbrack\ L\ _\ {i+1},U\ _\ {i+1}\rbrack\neq\emptyset\ (1\leq\ i\lt\ N) $ - $ 1\leq\ Q\leq2\times10\ ^\ 5 $ - $ 1\leq\ s\ _\ {x,i}\leq\ N $ かつ $ L\ _\ {s\ _\ {x,i}}\leq\ s\ _\ {y,i}\leq\ U\ _\ {s\ _\ {x,i}}\ (1\leq\ i\leq\ Q) $ - $ 1\leq\ t\ _\ {x,i}\leq\ N $ かつ $ L\ _\ {t\ _\ {x,i}}\leq\ t\ _\ {y,i}\leq\ U\ _\ {t\ _\ {x,i}}\ (1\leq\ i\leq\ Q) $ - 入力はすべて整数 ### Sample Explanation 1 与えられたマスは以下のようになります。 !\[\](https://img.atcoder.jp/abc365/4d07a40c98eda33ee86b773e564681c7.png) $ 1 $ つめの質問では、例えば以下のように移動することでマス $ (1,4) $ からマス $ (6,3) $ へ $ 10 $ 回の行動で移動することができます。 !\[\](https://img.atcoder.jp/abc365/4e579f6b171a642891732ae6efcdd550.png) $ 9 $ 回以下の行動でマス $ (1,4) $ からマス $ (6,3) $ へ移動することはできないため、$ 10 $ を出力してください。 ### Sample Explanation 2 出力すべき値が $ 32\operatorname{bit} $ 整数に収まらない場合があることに注意してください。