第22回日本情報オリンピック　二次予選

2022年12月13日
情報オリンピック日本委員会

問題文

JOI 中学校には 4N 人の一年生が在籍しており，4 つのクラスに分かれている．各クラスの情報は以下の通りである．

• 1 年 A 組： N 人の生徒がいる．それぞれの生徒の身長は A₁, A₂, …, A_N である．
• 1 年 B 組： N 人の生徒がいる．それぞれの生徒の身長は B₁, B₂, …, B_N である．
• 1 年 C 組： N 人の生徒がいる．それぞれの生徒の身長は C₁, C₂, …, C_N である．
• 1 年 D 組： N 人の生徒がいる．それぞれの生徒の身長は D₁, D₂, …, D_N である．

来月，JOI 中学校では体育祭が開催されることになった．体育祭には，リレー，騎馬戦，棒倒しなどの様々な種目があるが，各学年が踊るダンスは「体育祭の華」とも呼ばれる注目の種目である．

ここで一年生は，各クラスから代表を 1 人ずつ選び，4 人でダンスをすることになった．ダンスの見栄えをできるだけ良くするため，身長の差ができるだけ小さくなるように 4 人組を選ぶことにした．

一年生の身長が与えられるとき，「4 人の身長の最大値」と「4 人の身長の最小値」の差として考えられる最小の値を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 75 000．
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ B_j ≦ 10⁹ (1 ≦ j ≦ N)．
• 1 ≦ C_k ≦ 10⁹ (1 ≦ k ≦ N)．
• 1 ≦ D_l ≦ 10⁹ (1 ≦ l ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (7 点) N = 1．
2. (23 点) N ≦ 30．
3. (14 点) N ≦ 2 000，A_i ≦ 10 (1 ≦ i ≦ N)，B_j ≦ 10 (1 ≦ j ≦ N)，C_k ≦ 10 (1 ≦ k ≦ N)，D_l ≦ 10 (1 ≦ l ≦ N)．
4. (20 点) N ≦ 2 000，A_i ≦ 2 000 (1 ≦ i ≦ N)，B_j ≦ 2 000 (1 ≦ j ≦ N)，C_k ≦ 2 000 (1 ≦ k ≦ N)，D_l ≦ 2 000 (1 ≦ l ≦ N)．
5. (13 点) N ≦ 2 000．
6. (23 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁ A₂ … A_N
B₁ B₂ … B_N
C₁ C₂ … C_N
D₁ D₂ … D_N

出力

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

入出力例

入力例 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 の制約を満たす．