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$ 分）无其他附加限制 ### 样例解释 1 在第 $1$ 个方案中，展出的美术品价值依次为 $1, 2, 3, 4, 6, 7, 8, 9, 10, 11$。此时任意相邻两件展品价值差的最小值为 $1$。 该输入样例满足子任务1和3的约束。 ### 样例解释 2 该输入样例满足所有子任务的约束。 ### 样例解释 3 该输入样例满足子任务1和3的约束。 ### 约束条件 - 输入均为整数。 - $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)$ 由 ChatGPT 5 翻译