Tehtävänanto

JOI-yläkoulussa on $4N$ ensimmäisen vuoden oppilasta, jotka on jaettu $4$ luokkaan. Kunkin luokan tiedot ovat seuraavat:

• Luokka 1-A: Luokalla on $N$ oppilasta. Heidän pituutensa ovat $A_1, A_2, \dots, A_N$.
• Luokka 1-B: Luokalla on $N$ oppilasta. Heidän pituutensa ovat $B_1, B_2, \dots, B_N$.
• Luokka 1-C: Luokalla on $N$ oppilasta. Heidän pituutensa ovat $C_1, C_2, \dots, C_N$.
• Luokka 1-D: Luokalla on $N$ oppilasta. Heidän pituutensa ovat $D_1, D_2, \dots, D_N$.

Ensi kuussa JOI-yläkoulussa järjestetään urheilujuhla. Vaikka urheilujuhlassa on monenlaisia lajeja, kuten viestijuoksu, ratsuväkitaistelu ja paalunkaato, kunkin vuosiluokan esittämä tanssi on kohokohta, jota kutsutaan usein "urheilujuhlan kukaksi".

Tässä ensimmäisen vuoden oppilaat päättivät valita jokaiselta luokalta $1$ edustajan muodostamaan $4$ hengen tanssiryhmän. Jotta tanssi näyttäisi mahdollisimman hyvältä, he päättivät valita $4$ hengen ryhmän siten, että pituusero on mahdollisimman pieni.

Kun ensimmäisen vuoden oppilaiden pituudet on annettu, kirjoita ohjelma, joka etsii pienimmän mahdollisen arvon erotukselle "suurin pituus $4$ oppilaan joukossa" miinus "pienin pituus $4$ oppilaan joukossa".

Syöte

Syöte annetaan seuraavassa muodossa:

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

Tuloste

Tulosta $1$ riville pienin mahdollinen arvo erotukselle "suurin pituus $4$ oppilaan joukossa" miinus "pienin pituus $4$ oppilaan joukossa".

Rajoitukset

• $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$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($7$ pistettä) $N = 1$.
2. ($23$ pistettä) $N \le 30$.
3. ($14$ pistettä) $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$ pistettä) $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$ pistettä) $N \le 2\,000$.
6. ($23$ pistettä) Ei lisärajoituksia.

Esimerkit

Esimerkkisyöte 1

1
169
173
152
200

Esimerkkituloste 1

48

Koska $N = 1$, kaikki oppilaat on valittava muodostamaan $4$ hengen ryhmä. Tällöin suurin pituus $4$ oppilaan joukossa on $200$ ja pienin $152$, joten niiden erotus on $200 - 152 = 48$. Siispä tulostetaan $48$.

Tämä esimerkkisyöte täyttää osatehtävien $1, 2, 4, 5, 6$ rajoitukset.

Esimerkkisyöte 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

Esimerkkituloste 2

2

Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkkisyöte 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

Esimerkkituloste 3

0

Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkkisyöte 4

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

Esimerkkituloste 4

70

Tämä esimerkkisyöte täyttää osatehtävien $2, 4, 5, 6$ rajoitukset.

Esimerkkisyöte 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

Esimerkkituloste 5

79

Tämä esimerkkisyöte täyttää osatehtävien $2, 5, 6$ rajoitukset.