Deskripsi

Terdapat $4N$ siswa kelas satu yang terdaftar di SMP JOI, yang terbagi menjadi $4$ kelas. Informasi untuk masing-masing kelas adalah sebagai berikut:

• Kelas 1-A: Terdapat $N$ siswa. Tinggi badan masing-masing siswa adalah $A_1, A_2, \dots, A_N$.
• Kelas 1-B: Terdapat $N$ siswa. Tinggi badan masing-masing siswa adalah $B_1, B_2, \dots, B_N$.
• Kelas 1-C: Terdapat $N$ siswa. Tinggi badan masing-masing siswa adalah $C_1, C_2, \dots, C_N$.
• Kelas 1-D: Terdapat $N$ siswa. Tinggi badan masing-masing siswa adalah $D_1, D_2, \dots, D_N$.

Bulan depan, festival olahraga akan diadakan di SMP JOI. Meskipun festival olahraga mencakup berbagai cabang seperti lari estafet, perang kavaleri, dan merobohkan tiang, tarian yang dibawakan oleh setiap angkatan merupakan acara sorotan yang sering disebut sebagai "bunga festival olahraga".

Di sini, siswa kelas satu memutuskan untuk memilih $1$ perwakilan dari setiap kelas untuk membentuk kelompok beranggotakan $4$ orang untuk menari. Agar tarian terlihat sebagus mungkin, mereka memutuskan untuk memilih kelompok $4$ orang tersebut sedemikian sehingga selisih tinggi badannya sekecil mungkin.

Diberikan tinggi badan para siswa kelas satu, buatlah program untuk mencari nilai minimum yang mungkin dari selisih antara "tinggi badan maksimum di antara $4$ siswa" dan "tinggi badan minimum di antara $4$ siswa".

Masukan

Masukan diberikan dalam format berikut:

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

Keluaran

Keluarkan dalam $1$ baris nilai minimum yang mungkin dari selisih antara "tinggi badan maksimum di antara $4$ siswa" dan "tinggi badan minimum di antara $4$ siswa".

Batasan

• $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$).
• Semua nilai masukan adalah bilangan bulat.

Subsoal

1. ($7$ poin) $N = 1$.
2. ($23$ poin) $N \le 30$.
3. ($14$ poin) $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$ poin) $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$ poin) $N \le 2\,000$.
6. ($23$ poin) Tidak ada batasan tambahan.

Contoh

Contoh Masukan 1

1
169
173
152
200

Contoh Keluaran 1

48

Karena $N = 1$, semua siswa harus dipilih untuk membentuk kelompok $4$ orang. Pada saat ini, tinggi badan maksimum di antara $4$ siswa adalah $200$ dan tinggi badan minimum adalah $152$, sehingga selisihnya adalah $200 - 152 = 48$. Dengan demikian, keluarkan $48$.

Contoh masukan ini memenuhi batasan Subsoal $1, 2, 4, 5, 6$.

Contoh Masukan 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

Contoh Keluaran 2

2

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

Contoh Masukan 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

Contoh Keluaran 3

0

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

Contoh Masukan 4

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

Contoh Keluaran 4

70

Contoh masukan ini memenuhi batasan Subsoal $2, 4, 5, 6$.

Contoh Masukan 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

Contoh Keluaran 5

79

Contoh masukan ini memenuhi batasan Subsoal $2, 5, 6$.