题目描述

给出 $n$ 个数 ，对每个 $i\in [1,n]$，求出从他们中选出 $i$ 个得到的 gcd 的最大值。

输入格式

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

接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$。

输出格式

一行 $n-1$ 个正整数，第 $i$ 个为选出 $i+1$ 个的 gcd 的最大值。

样例

样例输入

5
1 2 3 4 6

样例输出

3 2 1 1

数据范围

对于所有数据，$1\le n,a_i\le 10^5$。