Beskrivelse

Det går $4N$ førsteårselever på JOI ungdomsskole, fordelt på $4$ klasser. Informasjonen for hver klasse er som følger:

• Klasse 1-A: Det er $N$ elever. Høydene deres er $A_1, A_2, \dots, A_N$.
• Klasse 1-B: Det er $N$ elever. Høydene deres er $B_1, B_2, \dots, B_N$.
• Klasse 1-C: Det er $N$ elever. Høydene deres er $C_1, C_2, \dots, C_N$.
• Klasse 1-D: Det er $N$ elever. Høydene deres er $D_1, D_2, \dots, D_N$.

Neste måned skal det arrangeres en idrettsfestival på JOI ungdomsskole. Selv om idrettsfestivalen inneholder ulike øvelser som stafett, rytterkamp og pålevelting, er dansen som hvert klassetrinn fremfører et høydepunkt som ofte kalles «idrettsfestivalens blomst».

Her bestemte førsteårselevene seg for å velge $1$ representant fra hver klasse for å danne en gruppe på $4$ personer til å danse. For at dansen skal ta seg så godt ut som mulig, bestemte de seg for å velge gruppen på $4$ slik at høydeforskjellen blir så liten som mulig.

Gitt høydene til førsteårselevene, skriv et program som finner den minste mulige verdien av forskjellen mellom «den største høyden blant de $4$ elevene» og «den minste høyden blant de $4$ elevene».

Inndata

Inndataene gis i følgende 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$ linje den minste mulige verdien av forskjellen mellom «den største høyden blant de $4$ elevene» og «den minste høyden blant de $4$ elevene».

Begrensninger

• $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 inndataverdier er heltall.

Deloppgaver

1. ($7$ poeng) $N = 1$.
2. ($23$ poeng) $N \le 30$.
3. ($14$ poeng) $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$ poeng) $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$ poeng) $N \le 2\,000$.
6. ($23$ poeng) Ingen ytterligere begrensninger.

Eksempler

Eksempel på inndata 1

1
169
173
152
200

Eksempel på utdata 1

48

Siden $N = 1$, må alle elevene velges for å danne gruppen på $4$. Da er den største høyden blant de $4$ elevene $200$ og den minste er $152$, så forskjellen er $200 - 152 = 48$. Dermed skrives $48$ ut.

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $1, 2, 4, 5, 6$.

Eksempel på inndata 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

Eksempel på utdata 2

2

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 3, 4, 5, 6$.

Eksempel på inndata 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

Eksempel på utdata 3

0

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 3, 4, 5, 6$.

Eksempel på inndata 4

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

Eksempel på utdata 4

70

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 4, 5, 6$.

Eksempel på inndata 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

Eksempel på utdata 5

79

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 5, 6$.