← 返回题目列表

Codeforces · 1176/D

D. 恢复它!

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

作者猜测数组 $$$a$$$ 由 $$$n$$$ 整数组成;每个整数不小于 $$$2$$$ 且不大于 $$$2 \cdot 10^5$$$。您不知道数组 $$$a$$$,但您知道数组 $$$b$$$,它是通过以下操作序列由它构成的:

1、首先让数组$$$b$$$等于数组$$$a$$$;
2. 其次,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$:如果 $$$a_i$$$ 是素数,则将一个整数 $$$p_{a_i}$$$ 追加到数组 $$$b$$$ 中,其中 $$$p$$$ 是素数的无限序列 ($$$2, 3, 5, \点$$$); 否则(如果 $$$a_i$$$ 不是素数),将 $$$a_i$$$ 不等于 $$$a_i$$$ 的最大除数附加到 $$$b$$$ 后;
3. 然后将获得的长度为 $$$2n$$$ 的数组打乱并在输入中提供给您。

这里 $$$p_{a_i}$$$ 表示第 $$$a_i$$$ 个质数。第一个素数 $$$p_1 = 2$$$,第二个素数 $$$p_2 = 3$$$,依此类推。

你的任务是恢复形成给定数组 $$$b$$$ 的任何合适的数组 $$$a$$$。保证答案存在(因此数组 $$$b$$$ 是从某个合适的数组 $$$a$$$ 获得的)。如果有多个答案,您可以打印任何一个。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。

输入的第二行包含 $$$2n$$$ 整数 $$$b_1, b_2, \dots, b_{2n}$$$ ($$$2 \le b_i \le 2750131$$$),其中 $$$b_i$$$ 是 $$$b$$$ 的第 $$$i$$$ 个元素。 $$$2750131$$$ 是第 $$$199999$$$ 个质数。

输出

在输出的唯一行中以任意顺序打印 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 2 \cdot 10^5$$$) — 数组 $$$a$$$,可以使用问题陈述中给出的移动顺序从中获得数组 $$$b$$$。如果有多个答案,您可以打印任何一个。

示例

输入 #1

3
3 5 2 3 2 4

输出 #1

3 4 2

输入 #2

1
2750131 199999

输出 #2

199999

输入 #3

1
3 6

输出 #3

6