وصف المسألة

يوجد $4N$ طالباً في السنة الأولى مسجلين في مدرسة JOI الإعدادية، وهم مقسمون إلى $4$ فصول. معلومات كل فصل هي كما يلي:

• الفصل 1-A: يوجد $N$ طلاب. أطوالهم هي $A_1, A_2, \dots, A_N$.
• الفصل 1-B: يوجد $N$ طلاب. أطوالهم هي $B_1, B_2, \dots, B_N$.
• الفصل 1-C: يوجد $N$ طلاب. أطوالهم هي $C_1, C_2, \dots, C_N$.
• الفصل 1-D: يوجد $N$ طلاب. أطوالهم هي $D_1, D_2, \dots, D_N$.

في الشهر القادم، سيُقام مهرجان رياضي في مدرسة JOI الإعدادية. على الرغم من أن المهرجان الرياضي يتضمن مسابقات متنوعة مثل التتابع ومعركة الفرسان وإسقاط العمود، إلا أن الرقصة التي يؤديها كل صف دراسي تُعد الحدث الأبرز الذي يُطلق عليه غالباً "زهرة المهرجان الرياضي".

هنا، قرر طلاب السنة الأولى اختيار ممثل $1$ من كل فصل لتشكيل مجموعة من $4$ طلاب للرقص. ولكي تبدو الرقصة بأفضل مظهر ممكن، قرروا اختيار المجموعة المكونة من $4$ طلاب بحيث يكون الفرق في الطول أصغر ما يمكن.

بمعرفة أطوال طلاب السنة الأولى، اكتب برنامجاً لإيجاد أصغر قيمة ممكنة للفرق بين "أقصى طول بين الطلاب الـ $4$" و"أدنى طول بين الطلاب الـ $4$".

الإدخال

يُعطى الإدخال بالصيغة التالية:

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

الإخراج

اطبع في سطر $1$ أصغر قيمة ممكنة للفرق بين "أقصى طول بين الطلاب الـ $4$" و"أدنى طول بين الطلاب الـ $4$".

القيود

• $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$).
• جميع قيم الإدخال هي أعداد صحيحة.

المهام الفرعية

1. ($7$ نقاط) $N = 1$.
2. ($23$ نقطة) $N \le 30$.
3. ($14$ نقطة) $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$ نقطة) $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$ نقطة) $N \le 2\,000$.
6. ($23$ نقطة) لا توجد قيود إضافية.

أمثلة

مثال الإدخال 1

1
169
173
152
200

مثال الإخراج 1

48

بما أن $N = 1$، يجب اختيار جميع الطلاب لتشكيل المجموعة المكونة من $4$ طلاب. عندئذٍ، يكون أقصى طول بين الطلاب الـ $4$ هو $200$ وأدنى طول هو $152$، وبالتالي فإن الفرق بينهما هو $200 - 152 = 48$. إذن، نطبع $48$.

يحقق مثال الإدخال هذا قيود المهام الفرعية $1, 2, 4, 5, 6$.

مثال الإدخال 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

مثال الإخراج 2

2

يحقق مثال الإدخال هذا قيود المهام الفرعية $2, 3, 4, 5, 6$.

مثال الإدخال 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

مثال الإخراج 3

0

يحقق مثال الإدخال هذا قيود المهام الفرعية $2, 3, 4, 5, 6$.

مثال الإدخال 4

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

مثال الإخراج 4

70

يحقق مثال الإدخال هذا قيود المهام الفرعية $2, 4, 5, 6$.

مثال الإدخال 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

مثال الإخراج 5

79

يحقق مثال الإدخال هذا قيود المهام الفرعية $2, 5, 6$.