조이 4인조

문제

JOI 중학교에는 $4N$ 명의 1학년이 재학 중이며, $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학년은 각 반에서 대표를 $1$ 명씩 뽑아, $4$ 명이 춤을 추기로 하였다. 춤이 최대한 보기 좋도록, 키 차이가 가능한 한 작아지도록 $4$ 인조를 뽑기로 하였다.

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$ 점) 추가 제약이 없다.

입력

입력은 다음과 같은 형식으로 주어진다.
$N$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$B_{1}$ $B_{2}$ $\dots$ $B_{N}$
$C_{1}$ $C_{2}$ $\dots$ $C_{N}$
$D_{1}$ $D_{2}$ $\dots$ $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$ 의 제약을 만족한다.