Đề bài

Trường THCS JOI có $4N$ học sinh năm nhất đang theo học, được chia thành $4$ lớp. Thông tin về mỗi lớp như sau:

• Lớp 1-A: Có $N$ học sinh. Chiều cao của từng học sinh lần lượt là $A_1, A_2, \dots, A_N$.
• Lớp 1-B: Có $N$ học sinh. Chiều cao của từng học sinh lần lượt là $B_1, B_2, \dots, B_N$.
• Lớp 1-C: Có $N$ học sinh. Chiều cao của từng học sinh lần lượt là $C_1, C_2, \dots, C_N$.
• Lớp 1-D: Có $N$ học sinh. Chiều cao của từng học sinh lần lượt là $D_1, D_2, \dots, D_N$.

Tháng sau, trường THCS JOI sẽ tổ chức đại hội thể thao. Đại hội thể thao có nhiều nội dung khác nhau như chạy tiếp sức, cưỡi ngựa đấu thương, lật cột, nhưng bài nhảy của mỗi khối là nội dung tâm điểm thường được gọi là "hoa của đại hội thể thao".

Tại đây, các học sinh năm nhất quyết định chọn $1$ đại diện từ mỗi lớp để tạo thành một nhóm $4$ người cùng nhảy. Để bài nhảy trông đẹp mắt nhất có thể, họ quyết định chọn nhóm $4$ người sao cho độ chênh lệch chiều cao là nhỏ nhất có thể.

Cho biết chiều cao của các học sinh năm nhất, hãy viết chương trình tìm giá trị nhỏ nhất có thể của hiệu giữa "chiều cao lớn nhất trong $4$ người" và "chiều cao nhỏ nhất trong $4$ người".

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

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

Dữ liệu ra

In ra trên $1$ dòng giá trị nhỏ nhất có thể của hiệu giữa "chiều cao lớn nhất trong $4$ người" và "chiều cao nhỏ nhất trong $4$ người".

Giới hạn

• $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$).
• Tất cả các giá trị đầu vào đều là số nguyên.

Subtask

1. ($7$ điểm) $N = 1$.
2. ($23$ điểm) $N \le 30$.
3. ($14$ điểm) $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$ điểm) $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$ điểm) $N \le 2\,000$.
6. ($23$ điểm) Không có giới hạn bổ sung.

Ví dụ

Ví dụ 1 - Dữ liệu vào

1
169
173
152
200

Ví dụ 1 - Dữ liệu ra

48

Vì $N = 1$, nên phải chọn tất cả học sinh để lập thành nhóm $4$ người. Khi đó, chiều cao lớn nhất trong $4$ người là $200$ và nhỏ nhất là $152$, hiệu của chúng là $200 - 152 = 48$. Do đó, in ra $48$.

Ví dụ này thỏa mãn các giới hạn của Subtask $1, 2, 4, 5, 6$.

Ví dụ 2 - Dữ liệu vào

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

Ví dụ 2 - Dữ liệu ra

2

Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 4, 5, 6$.

Ví dụ 3 - Dữ liệu vào

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

Ví dụ 3 - Dữ liệu ra

0

Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 4, 5, 6$.

Ví dụ 4 - Dữ liệu vào

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

Ví dụ 4 - Dữ liệu ra

70

Ví dụ này thỏa mãn các giới hạn của Subtask $2, 4, 5, 6$.

Ví dụ 5 - Dữ liệu vào

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

Ví dụ 5 - Dữ liệu ra

79

Ví dụ này thỏa mãn các giới hạn của Subtask $2, 5, 6$.