← 返回题目列表

Codeforces · 582/A

A. GCD 表

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

对于长度为 n 的正整数数组 a,大小为 n × n 的 GCD 表 G 由以下公式定义

$${ g _ { i j } = \operatorname* { g c d } ( a _ { i }, a _ { j } )。 }$$

让我们提醒您,两个正整数 x 和 y 的最大公约数 (GCD) 是 x 和 y 的约数中最大的整数,表示为 $$\gcd(x,y)$$。例如,对于长度为 4 的数组 a = {4, 3, 6, 2},GCD 表将如下所示:

给定GCD表G的所有数字,恢复数组a。

输入

第一行包含数字 n (1 ≤ n ≤ 500) — 数组 a 的长度。第二行包含 n2 个空格分隔的数字——数组 a 的 G 的 GCD 表的元素。

表中的所有数字均为正整数,不超过 109。请注意,元素以任意顺序给出。保证输入数据的集合对应于某个数组a。

输出

在单行中打印 n 个正整数 — 数组 a 的元素。如果有多种可能的解决方案,您可以打印其中任何一个。

示例

输入 #1

4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2

输出 #1

4 3 6 2

输入 #2

1
42

输出 #2

42

输入 #3

2
1 1 1 1

输出 #3

1 1