Aufgabenstellung

An der JOI-Mittelschule sind $4N$ Erstklässler eingeschrieben, die auf $4$ Klassen aufgeteilt sind. Die Informationen zu den einzelnen Klassen lauten wie folgt:

• Klasse 1-A: Es gibt $N$ Schüler. Ihre Körpergrößen betragen $A_1, A_2, \dots, A_N$.
• Klasse 1-B: Es gibt $N$ Schüler. Ihre Körpergrößen betragen $B_1, B_2, \dots, B_N$.
• Klasse 1-C: Es gibt $N$ Schüler. Ihre Körpergrößen betragen $C_1, C_2, \dots, C_N$.
• Klasse 1-D: Es gibt $N$ Schüler. Ihre Körpergrößen betragen $D_1, D_2, \dots, D_N$.

Nächsten Monat findet an der JOI-Mittelschule ein Sportfest statt. Obwohl das Sportfest verschiedene Disziplinen wie Staffellauf,Reiterspiele und Pfahlstürzen umfasst, ist der von jeder Jahrgangsstufe aufgeführte Tanz ein Höhepunkt, der oft als „Blume des Sportfests“ bezeichnet wird.

Hier haben die Erstklässler beschlossen, aus jeder Klasse jeweils $1$ Vertreter auszuwählen, um in einer Gruppe von $4$ Personen zu tanzen. Damit der Tanz so gut wie möglich aussieht, haben sie beschlossen, die $4$-er-Gruppe so zu wählen, dass der Größenunterschied so gering wie möglich ist.

Schreibe ein Programm, das anhand der Körpergrößen der Erstklässler den kleinstmöglichen Wert der Differenz zwischen der „maximalen Körpergröße unter den $4$ Schülern“ und der „minimalen Körpergröße unter den $4$ Schülern“ bestimmt.

Eingabe

Die Eingabe erfolgt im folgenden 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

Ausgabe

Gib in $1$ Zeile den kleinstmöglichen Wert der Differenz zwischen der „maximalen Körpergröße unter den $4$ Schülern“ und der „minimalen Körpergröße unter den $4$ Schülern“ aus.

Einschränkungen

• $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$).
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($7$ Punkte) $N = 1$.
2. ($23$ Punkte) $N \le 30$.
3. ($14$ Punkte) $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$ Punkte) $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$ Punkte) $N \le 2\,000$.
6. ($23$ Punkte) Keine weiteren Einschränkungen.

Beispiele

Eingabebeispiel 1

1
169
173
152
200

Ausgabebeispiel 1

48

Da $N = 1$ ist, müssen alle Schüler ausgewählt werden, um die $4$-er-Gruppe zu bilden. Dabei beträgt die maximale Körpergröße unter den $4$ Schülern $200$ und die minimale $152$, sodass ihre Differenz $200 - 152 = 48$ beträgt. Daher wird $48$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $1, 2, 4, 5, 6$.

Eingabebeispiel 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

Ausgabebeispiel 2

2

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4, 5, 6$.

Eingabebeispiel 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

Ausgabebeispiel 3

0

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4, 5, 6$.

Eingabebeispiel 4

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

Ausgabebeispiel 4

70

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 4, 5, 6$.

Eingabebeispiel 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

Ausgabebeispiel 5

79

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 5, 6$.