題目描述

JOI 中學有 $4N$ 名一年級學生，分為 $4$ 個班級。各班級的資訊如下：

• 1 年 A 班： 有 $N$ 名學生。每名學生的身高分別為 $A_1, A_2, \dots, A_N$。
• 1 年 B 班： 有 $N$ 名學生。每名學生的身高分別為 $B_1, B_2, \dots, B_N$。
• 1 年 C 班： 有 $N$ 名學生。每名學生的身高分別為 $C_1, C_2, \dots, C_N$。
• 1 年 D 班： 有 $N$ 名學生。每名學生的身高分別為 $D_1, D_2, \dots, D_N$。

下個月，JOI 中學將舉辦體育祭。體育祭有接力賽、騎馬戰、推桿比賽等各式各樣的項目，但由各個年級表演的舞蹈是被稱為「體育祭之花」的備受矚目項目。

在此，一年級決定從每個班級各選出 $1$ 名代表，組成 $4$ 人小組跳舞。為了讓舞蹈看起來盡可能美觀，他們決定選出使身高差盡可能小的 $4$ 人組。

給定一年級學生的身高，請編寫程式求出「$4$ 人身高的最大值」與「$4$ 人身高的最小值」之差可能的最小值。

輸入格式

輸入按以下格式給出：

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N
D_1 D_2 \ldots D_N

輸出格式

在 $1$ 行內輸出「$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$ 分）無額外限制。

範例

範例輸入 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$ 的限制。