分数: 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).
找到一组满足以下条件的整数。
- 可以通过如下方式获得:从一个空集开始,对于每个 i=1,2,\dots,N 按此顺序添加 A_i or B_i 到集合。
- 可以通过如下方式获得:从一个空集开始,对于每个 i=1,2,\dots,N 按此顺序添加 A_i or C_i 到集合。
- 满足上述两个条件的集合中元素数量最多。
约束
- 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,满足条件的整数集合中的元素数量,以及 x_i\ (1\leq i \leq k), k 集合的元素,格式如下:
k x_1 x_2 \dots x_k
如果多套满足条件,您可以打印其中任意套。
示例输入 1
3 1 1 1 2 3 4 5 4 2
示例输出 1
3 4 1 2
对于套装 \lbrace 1,2,4\rbrace,我们有以下内容。
- 满足第一个条件,因为您可以添加 B_1,A_2,B_3 到一个空集以获得这个集合。
- 满足第二个条件,因为您可以添加 A_1,C_2,C_3 到一个空集以获得这个集合。
显然,任何满足这些条件的集合最多有 N=3 元素,所以这个集合也满足第三个条件。
示例输入 2
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
示例输出 2
12 7 9 11 17 19 1 15 4 5 6 29 13