← 返回题目列表

AtCoder · arc156_f

F. 制作相同的套装

中文机器翻译题面 查看原题

分数: 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