Descrizione

Ci sono $4N$ studenti del primo anno iscritti alla scuola media JOI, divisi in $4$ classi. Le informazioni per ciascuna classe sono le seguenti:

• Classe 1-A: Ci sono $N$ studenti. Le loro altezze sono $A_1, A_2, \dots, A_N$.
• Classe 1-B: Ci sono $N$ studenti. Le loro altezze sono $B_1, B_2, \dots, B_N$.
• Classe 1-C: Ci sono $N$ studenti. Le loro altezze sono $C_1, C_2, \dots, C_N$.
• Classe 1-D: Ci sono $N$ studenti. Le loro altezze sono $D_1, D_2, \dots, D_N$.

Il mese prossimo si terrà il festival sportivo presso la scuola media JOI. Sebbene il festival sportivo comprenda varie specialità come la staffetta, la battaglia a cavallo e l'abbattimento del palo, il ballo eseguito da ciascun anno è un evento di punta spesso chiamato il "fiore del festival sportivo".

Qui, gli studenti del primo anno hanno deciso di scegliere $1$ rappresentante per ciascuna classe per formare un gruppo di $4$ persone che balleranno insieme. Per rendere il ballo il più gradevole possibile alla vista, hanno deciso di scegliere il gruppo di $4$ in modo che la differenza di altezza sia la più piccola possibile.

Date le altezze degli studenti del primo anno, scrivi un programma per trovare il minimo valore possibile della differenza tra "l'altezza massima tra i $4$ studenti" e "l'altezza minima tra i $4$ studenti".

Input

L'input è fornito nel seguente formato:

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

Output

Stampa su $1$ riga il minimo valore possibile della differenza tra "l'altezza massima tra i $4$ studenti" e "l'altezza minima tra i $4$ studenti".

Vincoli

• $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$).
• Tutti i valori di input sono interi.

Sottoproblemi

1. ($7$ punti) $N = 1$.
2. ($23$ punti) $N \le 30$.
3. ($14$ punti) $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$ punti) $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$ punti) $N \le 2\,000$.
6. ($23$ punti) Nessun vincolo aggiuntivo.

Esempi

Esempio di input 1

1
169
173
152
200

Esempio di output 1

48

Poiché $N = 1$, tutti gli studenti devono essere scelti per formare il gruppo di $4$. In questo caso, l'altezza massima tra i $4$ studenti è $200$ e la minima è $152$, quindi la loro differenza è $200 - 152 = 48$. Pertanto, si stampa $48$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $1, 2, 4, 5, 6$.

Esempio di input 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

Esempio di output 2

2

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 4, 5, 6$.

Esempio di input 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

Esempio di output 3

0

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 4, 5, 6$.

Esempio di input 4

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

Esempio di output 4

70

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 4, 5, 6$.

Esempio di input 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

Esempio di output 5

79

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 5, 6$.