You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

K-GCD

题目描述

给定$n$个正整数，求任选$k$个数的最大公约数的最大值。$k=1,2,...,n$。

注：一个数的最大公约数视为它自己。

输入格式

第一行一个正整数 $n$。

第二行为 $n$ 个空格隔开的正整数。

输出格式

总共 $n$ 行，第 $i$ 行为 $k=i$ 情况下的最大公约数的最大值。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

4
2
1
1

提示

数据范围

对于 $20\%$ 的数据，$n \leq 5$，$a_i\leq 10^3$；

对于另 $10\%$ 的数据，$n \leq 100$，$a_i \leq 10$；

对于 $60\%$ 的数据，$1\le n \leq 10^4$，$1\le a_i \leq 10^5$。

对于 $100\%$ 的数据，$1\le n \leq 10^5$，$1\le a_i \leq 10^6$。