题目描述

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
169
173
152
200

48

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

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

0

5
287 690 413 420 138
813 873 223 415 907
261 330 361 747 787
958 672 544 126 345

70

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

79

提示

数据范围

• $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 分）无额外约束。