Treść zadania

Do gimnazjum JOI uczęszcza $4N$ uczniów pierwszej klasy, podzielonych na $4$ klasy. Informacje o każdej klasie są następujące:

• Klasa 1-A: Liczy $N$ uczniów. Wzrost poszczególnych uczniów wynosi $A_1, A_2, \dots, A_N$.
• Klasa 1-B: Liczy $N$ uczniów. Wzrost poszczególnych uczniów wynosi $B_1, B_2, \dots, B_N$.
• Klasa 1-C: Liczy $N$ uczniów. Wzrost poszczególnych uczniów wynosi $C_1, C_2, \dots, C_N$.
• Klasa 1-D: Liczy $N$ uczniów. Wzrost poszczególnych uczniów wynosi $D_1, D_2, \dots, D_N$.

W przyszłym miesiącu w gimnazjum JOI odbędzie się festiwal sportowy. Choć festiwal obejmuje różne konkurencje, takie jak sztafeta, bitwa kawalerii czy obalanie słupa, taniec wykonywany przez każdy rocznik jest główną atrakcją, często nazywaną „kwiatem festiwalu sportowego”.

Pierwszoklasiści postanowili wybrać po $1$ reprezentancie z każdej klasy, aby utworzyć $4$-osobową grupę taneczną. Aby taniec prezentował się jak najlepiej, zdecydowali się dobrać $4$-osobową grupę tak, by różnica wzrostu była jak najmniejsza.

Mając dany wzrost uczniów pierwszej klasy, napisz program, który wyznaczy najmniejszą możliwą wartość różnicy między „maksymalnym wzrostem spośród $4$ uczniów” a „minimalnym wzrostem spośród $4$ uczniów”.

Wejście

Wejście podane jest w następującym formacie:

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

Wyjście

Wypisz w $1$ wierszu najmniejszą możliwą wartość różnicy między „maksymalnym wzrostem spośród $4$ uczniów” a „minimalnym wzrostem spośród $4$ uczniów”.

Ograniczenia

• $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$).
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($7$ punktów) $N = 1$.
2. ($23$ punkty) $N \le 30$.
3. ($14$ punktów) $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$ punktów) $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$ punktów) $N \le 2\,000$.
6. ($23$ punkty) Brak dodatkowych ograniczeń.

Przykłady

Przykład wejścia 1

1
169
173
152
200

Przykład wyjścia 1

48

Ponieważ $N = 1$, należy wybrać wszystkich uczniów, aby utworzyć $4$-osobową grupę. Wówczas maksymalny wzrost spośród $4$ uczniów wynosi $200$, a minimalny $152$, więc ich różnica wynosi $200 - 152 = 48$. Należy zatem wypisać $48$.

Ten przykład wejścia spełnia ograniczenia podzadań $1, 2, 4, 5, 6$.

Przykład wejścia 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

Przykład wyjścia 2

2

Ten przykład wejścia spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

Przykład wejścia 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

Przykład wyjścia 3

0

Ten przykład wejścia spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

Przykład wejścia 4

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

Przykład wyjścia 4

70

Ten przykład wejścia spełnia ograniczenia podzadań $2, 4, 5, 6$.

Przykład wejścia 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

Przykład wyjścia 5

79

Ten przykład wejścia spełnia ograniczenia podzadań $2, 5, 6$.