Énoncé

Il y a $4N$ élèves de première année inscrits au collège JOI, répartis en $4$ classes. Les informations concernant chaque classe sont les suivantes :

• Classe 1-A : Il y a $N$ élèves. Leurs tailles sont $A_1, A_2, \dots, A_N$.
• Classe 1-B : Il y a $N$ élèves. Leurs tailles sont $B_1, B_2, \dots, B_N$.
• Classe 1-C : Il y a $N$ élèves. Leurs tailles sont $C_1, C_2, \dots, C_N$.
• Classe 1-D : Il y a $N$ élèves. Leurs tailles sont $D_1, D_2, \dots, D_N$.

Le mois prochain, un festival sportif aura lieu au collège JOI. Bien que le festival sportif comprenne diverses épreuves telles que le relais, la bataille de cavalerie et la chute de poteau, la danse exécutée par chaque niveau est une épreuve phare souvent appelée la « fleur du festival sportif ».

Ici, les élèves de première année ont décidé de choisir $1$ représentant de chaque classe pour former un groupe de $4$ personnes pour danser. Afin que la danse soit aussi harmonieuse que possible, ils ont décidé de choisir le groupe de $4$ de sorte que l'écart de taille soit aussi petit que possible.

Étant donné les tailles des élèves de première année, écrivez un programme permettant de trouver la valeur minimale possible de la différence entre « la taille maximale parmi les $4$ élèves » et « la taille minimale parmi les $4$ élèves ».

Entrée

L'entrée est donnée dans le format suivant :

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

Sortie

Affichez sur $1$ ligne la valeur minimale possible de la différence entre « la taille maximale parmi les $4$ élèves » et « la taille minimale parmi les $4$ élèves ».

Contraintes

• $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$).
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

1. ($7$ points) $N = 1$.
2. ($23$ points) $N \le 30$.
3. ($14$ points) $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$ points) $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$ points) $N \le 2\,000$.
6. ($23$ points) Aucune contrainte supplémentaire.

Exemples

Exemple d'entrée 1

1
169
173
152
200

Exemple de sortie 1

48

Comme $N = 1$, tous les élèves doivent être choisis pour former le groupe de $4$. À ce moment-là, la taille maximale parmi les $4$ élèves est $200$ et la taille minimale est $152$, leur différence est donc $200 - 152 = 48$. Ainsi, on affiche $48$.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 2, 4, 5, 6$.

Exemple d'entrée 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

Exemple de sortie 2

2

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4, 5, 6$.

Exemple d'entrée 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

Exemple de sortie 3

0

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4, 5, 6$.

Exemple d'entrée 4

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

Exemple de sortie 4

70

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 4, 5, 6$.

Exemple d'entrée 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

Exemple de sortie 5

79

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 5, 6$.