AT_pakencamp_2022_day2_c Collaboration

パ研町にはパ研美術館とこまば美術館があります。それぞれの美術館には $ N $ 個の美術品が一列に展示されており、パ研美術館の左から $ i $ 番目の美術品の価値は $ A_i $ で、こまば美術館の左から $ i $ 番目の美術品の価値は $ B_i $ です。来場者をより楽しませるために、美術品は左から右に向かって価値の低い物から高い物の順に並んでいます。 パ研美術館とこまば美術館はコラボ展示をすることになりました。コラボには $ Q $ 個のプランがあり、 $ i $ 番目のプランでは、パ研美術館の左から $ L_i $ 番目から $ R_i $ 番目の美術品と、こまば美術館の左から $ X_i $ 番目から $ Y_i $ 番目の美術品を展示します。コラボ展示でも同様に、美術品は左から右に向かって価値の低い物から高い物の順に並べます。 ある展示の満足度を、隣り合う美術品の価値の差の最小値としましょう。各 $ i \ (1 \leq i \leq Q) $ について、 $ i $ 番目のプランで展示を行った際の満足度を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ Q $ $ L_1 $ $ R_1 $ $ X_1 $ $ Y_1 $ $ L_2 $ $ R_2 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ L_Q $ $ R_Q $ $ X_Q $ $ Y_Q $

$ Q $ 行に出力せよ。 $ i $ 行目 $ (1 \leq i \leq Q) $ には、 $ i $ 番目のプランで展示を行った際の満足度を出力せよ。

### 小課題 1. ( $ 50 $ 点) $ N, Q \leq 1000 $ 2. ( $ 150 $ 点) $ \max(A_{L_i}, B_{X_i}) > \min(A_{R_i}, B_{Y_i}) \ (1 \leq i \leq Q) $ 3. ( $ 400 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ 番目のプランでは、並ぶ美術品の価値は順に $ 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 $ です。この場合隣り合う展示品の価値の差の最小値は $ 1 $ となります。 この入力例は小課題 $ 1, 3 $ の制約を満たします。 ### Sample Explanation 2 この入力例は全ての小課題の制約を満たします。 ### Sample Explanation 3 この入力例は小課題 $ 1, 3 $ の制約を満たします。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 200000 $ - $ 1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^{18} $ - $ 1 \leq B_1 \leq B_2 \leq \cdots \leq B_N \leq 10^{18} $ - $ 1 \leq Q \leq 200000 $ - $ 1 \leq L_i \leq R_i \leq N \ (1 \leq i \leq Q) $ - $ 1 \leq X_i \leq Y_i \leq N \ (1 \leq i \leq Q) $