Description

There are $4N$ first-year students enrolled at JOI Junior High School, divided into $4$ classes. The information for each class is as follows:

• Class 1-A: There are $N$ students. Their heights are $A_1, A_2, \dots, A_N$.
• Class 1-B: There are $N$ students. Their heights are $B_1, B_2, \dots, B_N$.
• Class 1-C: There are $N$ students. Their heights are $C_1, C_2, \dots, C_N$.
• Class 1-D: There are $N$ students. Their heights are $D_1, D_2, \dots, D_N$.

Next month, a sports festival will be held at JOI Junior High School. Although the sports festival includes various events such as relays, cavalry battles, and pole toppling, the dance performed by each grade is a highlight event often called the "flower of the sports festival."

Here, the first-year students decided to choose $1$ representative from each class to form a group of $4$ to dance. To make the dance look as good as possible, they decided to choose the group of $4$ so that the difference in height is as small as possible.

Given the heights of the first-year students, write a program to find the minimum possible value of the difference between "the maximum height among the $4$ students" and "the minimum height among the $4$ students."

Input

The input is given in the following format:

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

Output

Output on $1$ line the minimum possible value of the difference between "the maximum height among the $4$ students" and "the minimum height among the $4$ students."

Constraints

• $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$).
• All input values are integers.

Subtasks

1. ($7$ points) $N = 1$.
2. ($23$ points) $N \le 30$.
3. ($14$ points) $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$ points) $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$ points) $N \le 2\,000$.
6. ($23$ points) No additional constraints.

Sample

Sample Input 1

1
169
173
152
200

Sample Output 1

48

Since $N = 1$, all students must be chosen to form the group of $4$. At this time, the maximum height among the $4$ students is $200$ and the minimum height is $152$, so their difference is $200 - 152 = 48$. Thus, output $48$.

This sample input satisfies the constraints of Subtasks $1, 2, 4, 5, 6$.

Sample Input 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

Sample Output 2

2

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.

Sample Input 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

Sample Output 3

0

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.

Sample Input 4

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

Sample Output 4

70

This sample input satisfies the constraints of Subtasks $2, 4, 5, 6$.

Sample Input 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

Sample Output 5

79

This sample input satisfies the constraints of Subtasks $2, 5, 6$.