对于长度为 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