配点 : 600 点
問題文
帕肯镇是帕肯艺术博物馆和驹场艺术博物馆的所在地。每个博物馆都有 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)
小課題
- (50 点) N, Q \leq 1000
- (150 点) \max(A_{L_i}, B_{X_i}) > \min(A_{R_i}, B_{Y_i}) \ (1 \leq i \leq Q)
- (400 点)无附加约束
入力
输入将以以下格式从标准输入给出。
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 输出第h个计划参展时的满意度。 在第
入力例 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 约束。