Quartet (JOI04)

Problem Statement

JOI Junior High School has 4N first-year students, who are divided into 4 classes. The information for each class is as follows.

• Class 1-A: There are N students. The heights of the students are A₁, A₂, ... , A_N.
• Class 1-B: There are N students. The heights of the students are B₁, B₂, ... , B_N.
• Class 1-C: There are N students. The heights of the students are C₁, C₂, ... , C_N.
• Class 1-D: There are N students. The heights of the students are D₁, D₂, ... , D_N.

Next month, JOI Junior High School will hold its sports day. The sports day features various events such as relays, horse races, and stick toppling, but the dance performed by each grade is a highlight often called "the flower of the sports day."

The first-year students will select one representative from each class to form a group of 4 who will perform the dance. To make the dance look as good as possible, they decided to choose the group of 4 so that the difference in their heights 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 and the minimum height among the 4 selected students.

Constraints

• 1 \leq N \leq 75000.
• 1 \leq A_i \leq 10⁹ (1 \leq i \leq N).
• 1 \leq B_j \leq 10⁹ (1 \leq j \leq N).
• 1 \leq C_k \leq 10⁹ (1 \leq k \leq N).
• 1 \leq D_l \leq 10⁹ (1 \leq l \leq N).
• All input values are integers.

Input

The input is given in the following format.
N
A₁ A₂ … A_N
B₁ B₂ … B_N
C₁ C₂ … C_N
D₁ D₂ … D_N

Output

Output the minimum possible value of the difference between the maximum height and the minimum height among the 4 selected students in one line.

Sample Input and Output

Sample Input 1

1
169
173
152
200

Sample Output 1

48

Since N = 1, all students must be selected to form the group of 4. In this case, the maximum height among the 4 students is 200 and the minimum height is 152, so the difference is 200 - 152 = 48. Therefore, output 48.

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

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

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

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

---