配点: 100 点
問題文
JOI初中 4N 一年级学生入学,4 它分为两类。各班级的信息如下。
- 第一年 A 组: 有 N 名学生。每个学生的身高为 A_1, A_2, \ldots, A_N 。
- 第一年 B 组: N 名学生。每个学生的身高为 B_1, B_2, \ldots, B_N 。
- 一年级C级: N 名学生。每个学生的身高为 C_1, C_2, \ldots, C_N 。
- 第一年 D 组: N 名学生。每个学生的身高为 D_1, D_2, \ldots, D_N 。
下个月JOI初中将举办体育节。体育节上有接力赛、骑兵赛、菩提舞等各种项目,但最受欢迎的是各年级表演的舞蹈,也被称为“体育节之花”。
在这里,一年级学生将被要求从每个班级中选出一名代表。 1 一次选择一个人,4 我们决定一起跳舞。为了使舞蹈看起来尽可能优美,身高差应尽可能小。 4 我决定选择一群人。
当给出一年级学生的身高时,4 人类最大身高”和“4 编写一个程序来找出人们的最小身高之间的最小可能差异。
制約
- 1 \leqq N \leqq 75\,000.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq B_j \leqq 10^9 (1 \leqq j \leqq N).
- 1 \leqq C_k \leqq 10^9 (1 \leqq k \leqq N).
- 1 \leqq D_l \leqq 10^9 (1 \leqq l \leqq N).
- 所有输入值均为整数。
小課題
- (7 点) N = 1.
- (23 点) N \leqq 30.
- (14 点) N \leqq 2\,000,A_i \leqq 10 (1 \leqq i \leqq N),B_j \leqq 10 (1 \leqq j \leqq N),C_k \leqq 10 (1 \leqq k \leqq N),D_l \leqq 10 (1 \leqq l \leqq N).
- (20 点) N \leqq 2\,000,A_i \leqq 2\,000 (1 \leqq i \leqq N),B_j \leqq 2\,000 (1 \leqq j \leqq N),C_k \leqq 2\,000 (1 \leqq k \leqq N),D_l \leqq 2\,000 (1 \leqq l \leqq N).
- (13 点) N \leqq 2\,000.
- (23 点)没有额外的限制。
入力
输入按以下格式给出。
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 行。
入力例 1
1 169 173 152 200
出力例 1
48
N = 1 因此,选择所有学生并 4 我们必须组建一群人。这时,4 人的最大身高是 200,最小值为 152 区别在于 200 - 152 = 48 。因此,48 。
此输入示例是一个小作业。 1, 2, 4, 5, 6 满足约束。
入力例 2
7 7 9 9 4 6 3 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 2
2
此输入示例是一个小作业。 2, 3, 4, 5, 6 满足约束。
入力例 3
7 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2
出力例 3
0
此输入示例是一个小作业。 2, 3, 4, 5, 6 满足约束。
入力例 4
5 287 690 413 420 138 813 873 223 415 907 261 330 361 747 787 958 672 544 126 345
出力例 4
70
此输入示例是一个小作业。 2, 4, 5, 6 满足约束。
入力例 5
10 1682 2008 1135 1576 2450 1362 1518 1925 2212 1275 1993 1945 1312 1401 2027 1705 1086 2333 1787 1654 2257 1548 1219 1031 2613 2171 1866 1532 2800 1497 1062 1175 1984 1870 2059 1639 2107 1335 1289 2494
出力例 5
79
此输入示例是一个小作业。 2, 5, 6 满足约束。