配点 : $1000$ 点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N),C=(C_1,C_2,\dots,C_N)$ が与えられます。

整数からなる集合のうち、以下の条件を満たすものを $1$ つ求めてください。

• 空集合に対し $i=1,2,\dots,N$ の順に $A_i,B_i$ のいずれかを追加していくことで得られる集合である。
• 空集合に対し $i=1,2,\dots,N$ の順に $A_i,C_i$ のいずれかを追加していくことで得られる集合である。
• 上記の $2$ つの条件を満たす集合の中で、要素数が最大である。

制約

• $1 \leq N \leq 5000$
• $1 \leq A_i,B_i,C_i \leq 10000$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

$C_1$ $C_2$ $\dots$ $C_N$

出力

条件を満たす整数集合の要素数 $k$ と、整数集合の $k$ 個の要素 $x_i\ (1\leq i \leq k)$ を以下の形式で出力せよ。

$k$

$x_1$ $x_2$ $\dots$ $x_k$

条件を満たす整数集合が複数存在する場合、いずれを出力してもかまわない。

3
1 1 1
2 3 4
5 4 2

3
4 1 2

集合 $\lbrace 1,2,4\rbrace$ は

• $1$ 番目の条件について、空集合に $B_1,A_2,B_3$ を追加することで得られます。
• $2$ 番目の条件について、空集合に $A_1,C_2,C_3$ を追加することで得られます。

条件を満たす集合の要素数は明らかに $N=3$ 以下であるため、この集合は $3$ 番目の条件も満たしています。

15
1 1 15 11 13 7 7 1 6 1 5 7 4 9 8
11 30 1 18 16 15 19 17 3 27 22 7 21 29 9
24 14 23 17 18 16 9 12 10 5 26 29 20 19 11

12
7 9 11 17 19 1 15 4 5 6 29 13