AT_joi2023_yo2_b ジョイ四人組 (JOI04)

JOI 中学校には $ 4N $ 人の一年生が在籍しており， $ 4 $ つのクラスに分かれている．各クラスの情報は以下の通りである． - **1 年 A 組：** $ N $ 人の生徒がいる．それぞれの生徒の身長は $ A_1, A_2, \ldots, A_N $ である． - **1 年 B 組：** $ N $ 人の生徒がいる．それぞれの生徒の身長は $ B_1, B_2, \ldots, B_N $ である． - **1 年 C 組：** $ N $ 人の生徒がいる．それぞれの生徒の身長は $ C_1, C_2, \ldots, C_N $ である． - **1 年 D 組：** $ N $ 人の生徒がいる．それぞれの生徒の身長は $ D_1, D_2, \ldots, D_N $ である． 来月，JOI 中学校では体育祭が開催されることになった．体育祭には，リレー，騎馬戦，棒倒しなどの様々な種目があるが，各学年が踊るダンスは「体育祭の華」とも呼ばれる注目の種目である． ここで一年生は，各クラスから代表を $ 1 $ 人ずつ選び， $ 4 $ 人でダンスをすることになった．ダンスの見栄えをできるだけ良くするため，身長の差ができるだけ小さくなるように $ 4 $ 人組を選ぶことにした． 一年生の身長が与えられるとき，「 $ 4 $ 人の身長の最大値」と「 $ 4 $ 人の身長の最小値」の差として考えられる最小の値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_N $ $ D_1 $ $ D_2 $ $ \cdots $ $ D_N $

「 $ 4 $ 人の身長の最大値」と「 $ 4 $ 人の身長の最小値」の差として考えられる最小の値を $ 1 $ 行で出力せよ．

### 小課題 1. ( $ 7 $ 点) $ N = 1 $ ． 2. ( $ 23 $ 点) $ N \leqq 30 $ ． 3. ( $ 14 $ 点) $ N \leqq 2\,000 $ ， $ A_i \leqq 10 $ ( $ 1 \leqq i \leqq N $ )， $ B_j \leqq 10 $ ( $ 1 \leqq j \leqq N $ )， $ C_k \leqq 10 $ ( $ 1 \leqq k \leqq N $ )， $ D_l \leqq 10 $ ( $ 1 \leqq l \leqq N $ )． 4. ( $ 20 $ 点) $ N \leqq 2\,000 $ ， $ A_i \leqq 2\,000 $ ( $ 1 \leqq i \leqq N $ )， $ B_j \leqq 2\,000 $ ( $ 1 \leqq j \leqq N $ )， $ C_k \leqq 2\,000 $ ( $ 1 \leqq k \leqq N $ )， $ D_l \leqq 2\,000 $ ( $ 1 \leqq l \leqq N $ )． 5. ( $ 13 $ 点) $ N \leqq 2\,000 $ ． 6. ( $ 23 $ 点) 追加の制約はない． ### Sample Explanation 1 $ N = 1 $ なので，全員の生徒を選んで $ 4 $ 人組を作らなければならない．このとき， $ 4 $ 人の身長の最大値は $ 200 $ ，最小値は $ 152 $ となり，その差は $ 200 - 152 = 48 $ である．よって， $ 48 $ を出力する． この入力例は小課題 $ 1, 2, 4, 5, 6 $ の制約を満たす． ### Sample Explanation 2 この入力例は小課題 $ 2, 3, 4, 5, 6 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 2, 3, 4, 5, 6 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 2, 4, 5, 6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 2, 5, 6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 75\,000 $ ． - $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq B_j \leqq 10^9 $ ( $ 1 \leqq j \leqq N $ )． - $ 1 \leqq C_k \leqq 10^9 $ ( $ 1 \leqq k \leqq N $ )． - $ 1 \leqq D_l \leqq 10^9 $ ( $ 1 \leqq l \leqq N $ )． - 入力される値はすべて整数である．