問題文

パ研町にはパ研美術館とこまば美術館があります。それぞれの美術館には N 個の美術品が一列に展示されており、パ研美術館の左から i 番目の美術品の価値は A_i で、こまば美術館の左から i 番目の美術品の価値は B_i です。来場者をより楽しませるために、美術品は左から右に向かって価値の低い物から高い物の順に並んでいます。

パ研美術館とこまば美術館はコラボ展示をすることになりました。コラボには Q 個のプランがあり、 i 番目のプランでは、パ研美術館の左から L_i 番目から R_i 番目の美術品と、こまば美術館の左から X_i 番目から Y_i 番目の美術品を展示します。コラボ展示でも同様に、美術品は左から右に向かって価値の低い物から高い物の順に並べます。

ある展示の満足度を、隣り合う美術品の価値の差の最小値としましょう。各 i \ (1 \leq i \leq Q) について、 i 番目のプランで展示を行った際の満足度を求めてください。

制約

• 入力は全て整数
• 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)

小課題

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 点) 追加の制約はない

入力例 1

6
1 3 6 8 9 11
2 2 4 7 10 11
4
1 6 2 5
1 6 5 5
2 5 5 5
4 6 3 6

出力例 1

1
1
1
0

1 番目のプランでは、並ぶ美術品の価値は順に 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 です。この場合隣り合う展示品の価値の差の最小値は 1 となります。

この入力例は小課題 1, 3 の制約を満たします。

入力例 2

10
4 14 18 31 47 51 59 72 78 96
2 23 25 36 58 60 63 85 88 97
7
1 3 5 5
6 10 3 4
8 10 1 4
7 10 2 4
6 7 1 3
2 4 6 9
2 3 2 9

出力例 2

4
6
2
2
2
3
2

この入力例は全ての小課題の制約を満たします。

入力例 3

15
1141 1334 2083 2504 4031 4238 4328 5260 5315 6427 6991 8127 8199 8356 9136
189 403 1035 1126 1165 1477 2021 2100 2528 3892 4108 4459 5792 7050 8709
8
4 7 7 15
8 11 8 11
7 11 2 15
2 13 6 11
11 12 3 10
8 10 3 12
3 11 3 10
3 11 8 10

出力例 3

24
55
39
17
39
39
17
17

この入力例は小課題 1, 3 の制約を満たします。