레이팅 미적용JOI 中学校には 4N 人の一年生が在籍しており, 4 つのクラスに分かれている.各クラスの情報は以下の通りである.
1 年 A 組: N 人の生徒がいる.それぞれの生徒の身長は A 1 , A 2 , ..., A N である.
1 年 B 組: N 人の生徒がいる.それぞれの生徒の身長は B 1 , B 2 , ..., B N である.
1 年 C 組: N 人の生徒がいる.それぞれの生徒の身長は C 1 , C 2 , ..., C N である.
1 年 D 組: N 人の生徒がいる.それぞれの生徒の身長は D 1 , D 2 , ..., D N である.
来月,JOI 中学校では体育祭が開催されることになった.体育祭には,リレー,騎馬戦,棒倒しなどの様々な種目があるが,各学年が踊るダンスは「体育祭の華」とも呼ばれる注目の種目である.
ここで一年生は,各クラスから代表を 1 人ずつ選び, 4 人でダンスをすることになった.ダンスの見栄えをできるだけ良くするため,身長の差ができるだけ小さくなるように 4 人組を選ぶことにした.
一年生の身長が与えられるとき,「 4 人の身長の最大値」と「 4 人の身長の最小値」の差として考えられる最小の値を求めるプログラムを作成せよ.
1 ≦ N ≦ 75 000 .
1 ≦ A i ≦ 10 9 ( 1 ≦ i ≦ N ).
1 ≦ B j ≦ 10 9 ( 1 ≦ j ≦ N ).
1 ≦ C k ≦ 10 9 ( 1 ≦ k ≦ N ).
1 ≦ D l ≦ 10 9 ( 1 ≦ l ≦ N ).
入力される値はすべて整数である.
( 7 点) N = 1 .
( 23 点) N ≦ 30 .
( 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 ).
( 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 ).
( 13 点) N ≦ 2 000 .
( 23 点) 追加の制約はない.
入力は以下の形式で与えられる.
N
A 1 A 2 ... A N
B 1 B 2 ... B N
C 1 C 2 ... C N
D 1 D 2 ... D N
「 4 人の身長の最大値」と「 4 人の身長の最小値」の差として考えられる最小の値を 1 行で出力せよ.
1
169
173
152
200
48
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
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
0
5
287 690 413 420 138
813 873 223 415 907
261 330 361 747 787
958 672 544 126 345
70
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
79