P14298 [JOI2023 预选赛 R2] JOI 运动会 / JOI04

JOI 中学有 $4N$ 名一年级学生，他们被分入 4 个班级。各班级的信息如下： - 1 年 A 组：有 $N$ 名学生，他们的身高分别为 $A_1, A_2, \cdots, A_N$。 - 1 年 B 组：有 $N$ 名学生，他们的身高分别为 $B_1, B_2, \cdots, B_N$。 - 1 年 C 组：有 $N$ 名学生，他们的身高分别为 $C_1, C_2, \cdots, C_N$。 - 1 年 D 组：有 $N$ 名学生，他们的身高分别为 $D_1, D_2, \cdots, D_N$。 下个月，JOI 中学将举办运动会。运动会包含接力、骑马战、棒倒等多种项目，而各年级表演的舞蹈被称为“运动会之花”，是备受瞩目的项目。 为此，一年级学生将从每个班级各选一名代表，组成 4 人小组进行舞蹈表演。为了使舞蹈表演更具观赏性，他们决定选择身高差尽可能小的 4 人组合。 给定一年级学生的身高数据，请编写一个程序，求出“4 人身高最大值”与“4 人身高最小值”之差的最小可能值

输入数据按以下格式给出： $N$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$ $C_1\ C_2\ \cdots\ C_N$ $D_1\ D_2\ \cdots\ D_N$

在一行内输出“4 人身高最大值”与“4 人身高最小值”之差的最小可能值。

### 数据范围 - $1 \le N \le 75\,000$。 - $1 \le A_i \le 10^9$（$1 \le i \le N$）。 - $1 \le B_j \le 10^9$（$1 \le j \le N$）。 - $1 \le C_k \le 10^9$（$1 \le k \le N$）。 - $1 \le D_l \le 10^9$（$1 \le l \le N$）。 - 所有输入值均为整数。 ### 子任务 1. （7 分）$N = 1$。 2. （23 分）$N \le 30$。 3. （14 分）$N \le 2\,000$，且 $A_i \le 10$（$1 \le i \le N$），$B_j \le 10$（$1 \le j \le N$），$C_k \le 10$（$1 \le k \le N$），$D_l \le 10$（$1 \le l \le N$）。 4. （20 分）$N \le 2\,000$，且 $A_i \le 2\,000$（$1 \le i \le N$），$B_j \le 2\,000$（$1 \le j \le N$），$C_k \le 2\,000$（$1 \le k \le N$），$D_l \le 2\,000$（$1 \le l \le N$）。 5. （13 分）$N \le 2\,000$。 6. （23 分）无额外约束。