题目描述

在育华学校的毕业文艺汇演筹备过程中，老师对同学们的表演阵容进行了重新评估。之 前按照取每位同学的号数来衡量默契程度（找最大公约数）不太合理，所以老师给每位 同学评定了一个能力值。现在的问题是，从 $n$ 个参与表演的同学中挑选出 $k$ 个人（$1\leq k\leq n$） ， 使得这 $k$ 个人的能力值的最大公约数最大。由于表演节目多样，每个节目所需的人 数不确定，老师希望知道对于 $k$ 从 $1$ 到 $n$ 的各种情况下，能达到的最大默契 程度（即最大公约数）分别是多少。请你编写程序来解决这个问题。

注意：一个数的最大公约数就是它本身。

输入格式

第一行包含一个正整数 $n$，表示参与表演的同学数量。

第二行包含 $n$ 个用空格分隔的正整数，表示每个同学的能力值。

输出格式

总共输出 $n$ 行，第 $i$ 行表示当 $k = i$ 时的最大默契程度。

样例 #1

样例输入 #1

5
3 6 9 12 15

样例输出 #1

15
6
3
3
3

提示

【数据范围】

记输入数据中能力值的最大值为 $inf$。

• 对于 $20\%$ 的数据，$n\leq 5$，$inf\leq 10^{3}$；
• 对于另 $30\%$ 的数据，$n\leq 100$，$inf\leq 10$；
• 对于 $100\%$ 的数据，$n\leq 10^{4}$，$inf\leq 10^{6}$。