Beskrivning

Det går $4N$ förstaårselever på JOI-högstadieskolan, uppdelade i $4$ klasser. Informationen för varje klass är följande:

• Klass 1-A: Det finns $N$ elever. Deras längder är $A_1, A_2, \dots, A_N$.
• Klass 1-B: Det finns $N$ elever. Deras längder är $B_1, B_2, \dots, B_N$.
• Klass 1-C: Det finns $N$ elever. Deras längder är $C_1, C_2, \dots, C_N$.
• Klass 1-D: Det finns $N$ elever. Deras längder är $D_1, D_2, \dots, D_N$.

Nästa månad ska en idrottsfestival hållas på JOI-högstadieskolan. Även om idrottsfestivalen innehåller olika grenar som stafett, ryttarstrid och pålvältning, är dansen som varje årskurs framför en höjdpunkt som ofta kallas "idrottsfestivalens blomma".

Här bestämde sig förstaårseleverna för att välja $1$ representant från varje klass för att bilda en grupp på $4$ personer som ska dansa. För att dansen ska se så bra ut som möjligt bestämde de sig för att välja gruppen på $4$ så att längdskillnaden blir så liten som möjligt.

Givet längderna på förstaårseleverna, skriv ett program som hittar det minsta möjliga värdet på skillnaden mellan "den största längden bland de $4$ eleverna" och "den minsta längden bland de $4$ eleverna".

Indata

Indata ges i följande 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

Utdata

Skriv ut på $1$ rad det minsta möjliga värdet på skillnaden mellan "den största längden bland de $4$ eleverna" och "den minsta längden bland de $4$ eleverna".

Begränsningar

• $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$).
• Alla indatavärden är heltal.

Deluppgifter

1. ($7$ poäng) $N = 1$.
2. ($23$ poäng) $N \le 30$.
3. ($14$ poäng) $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$ poäng) $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$ poäng) $N \le 2\,000$.
6. ($23$ poäng) Inga ytterligare begränsningar.

Exempel

Indataexempel 1

1
169
173
152
200

Utdataexempel 1

48

Eftersom $N = 1$ måste alla elever väljas för att bilda gruppen på $4$. Då är den största längden bland de $4$ eleverna $200$ och den minsta är $152$, så skillnaden är $200 - 152 = 48$. Alltså skrivs $48$ ut.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $1, 2, 4, 5, 6$.

Indataexempel 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

Utdataexempel 2

2

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4, 5, 6$.

Indataexempel 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

Utdataexempel 3

0

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4, 5, 6$.

Indataexempel 4

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

Utdataexempel 4

70

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 4, 5, 6$.

Indataexempel 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

Utdataexempel 5

79

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 5, 6$.