Lýsing

Í JOI-gagnfræðaskólanum eru $4N$ nemendur á fyrsta ári, sem skipt er í $4$ bekki. Upplýsingar um hvern bekk eru sem hér segir:

• Bekkur 1-A: Þar eru $N$ nemendur. Hæðir þeirra eru $A_1, A_2, \dots, A_N$.
• Bekkur 1-B: Þar eru $N$ nemendur. Hæðir þeirra eru $B_1, B_2, \dots, B_N$.
• Bekkur 1-C: Þar eru $N$ nemendur. Hæðir þeirra eru $C_1, C_2, \dots, C_N$.
• Bekkur 1-D: Þar eru $N$ nemendur. Hæðir þeirra eru $D_1, D_2, \dots, D_N$.

Í næsta mánuði verður haldin íþróttahátíð í JOI-gagnfræðaskólanum. Þótt íþróttahátíðin innihaldi ýmsar greinar eins og boðhlaup, riddarabardaga og staurafellingu, þá er dansinn sem hver árgangur stígur hápunktur sem oft er kallaður „blóm íþróttahátíðarinnar“.

Hér ákváðu nemendur á fyrsta ári að velja $1$ fulltrúa úr hverjum bekk til að mynda $4$ manna hóp til að dansa. Til að dansinn líti sem best út ákváðu þeir að velja $4$ manna hópinn þannig að hæðarmunurinn verði sem minnstur.

Gefið hæðir nemenda á fyrsta ári, skrifið forrit til að finna minnsta mögulega gildið á mismuninum á „hæstu hæð meðal nemendanna $4$“ og „lægstu hæð meðal nemendanna $4$“.

Inntak

Inntakið er gefið á eftirfarandi sniði:

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

Úttak

Prentið í $1$ línu minnsta mögulega gildið á mismuninum á „hæstu hæð meðal nemendanna $4$“ og „lægstu hæð meðal nemendanna $4$“.

Takmarkanir

• $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$).
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($7$ stig) $N = 1$.
2. ($23$ stig) $N \le 30$.
3. ($14$ stig) $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$ stig) $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$ stig) $N \le 2\,000$.
6. ($23$ stig) Engar viðbótartakmarkanir.

Dæmi

Inntaksdæmi 1

1
169
173
152
200

Úttaksdæmi 1

48

Þar sem $N = 1$ þarf að velja alla nemendurna til að mynda $4$ manna hópinn. Þá er hæsta hæðin meðal nemendanna $4$ jöfn $200$ og sú lægsta $152$, þannig að mismunurinn er $200 - 152 = 48$. Því er prentað $48$.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 2, 4, 5, 6$.

Inntaksdæmi 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

Úttaksdæmi 2

2

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 4, 5, 6$.

Inntaksdæmi 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

Úttaksdæmi 3

0

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 4, 5, 6$.

Inntaksdæmi 4

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

Úttaksdæmi 4

70

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 4, 5, 6$.

Inntaksdæmi 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

Úttaksdæmi 5

79

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 5, 6$.