著名核物理专家 Picks 提出了核聚变特征值这一重要概念。
核聚变特征值分别为 $x$ 和 $y$ 的两个原子进行核聚变，能产生数值为 $\text{sgcd}(x, y)$ 的核聚变反应强度。
其中， $\text{sgcd}(x, y)$ 表示 $x$ 和 $y$ 的次大公约数，即能同时整除 $x, y$ 的正整数中第二大的数。如果次大公约数不存在则说明无法核聚变， 此时 $\text{sgcd}(x, y) = -1$。
现在有 $n$ 个原子，核聚变特征值分别为 $a_1, a_2, \dots, a_n$。然后 Picks 又从兜里掏出一个核聚变特征值为 $a_1$ 的原子，你需要计算出这个原子与其它 $n$ 个原子分别进行核聚变反应时的核聚变反应强度，即 $\text{sgcd}(a_1, a_1), \text{sgcd}(a_1, a_2), \dots, \text{sgcd}(a_1, a_n)$。
输入格式
第一行一个正整数 $n$。
第二行 $n$ 个用空格隔开的正整数，第 $i$ 个为 $a_i$。
输出格式
一行 $n$ 个用空格隔开的整数，第 $i$ 个表示 $\text{sgcd}(a_1, a_i)$。
C/C++ 输入输出 long long 时请用 %lld。由于本题数据量较大，建议不要使用 cin/cout 进行输入输出。
样例一
input
4 12450 1 2 450
output
6225 -1 1 75
样例二
input
8 30030 6 10 12 55 36 450 666
output
15015 3 5 3 11 3 15 3
样例三
见样例数据下载。
限制与约定
| 测试点编号 | $n$、$a_i$的规模 |
|---|---|
| 1 | $n = 1$，$a_i \le 10^9$ |
| 2 | |
| 3 | $n \le 10^4$，$a_i \le 10^9$ |
| 4 | |
| 5 | |
| 6 | |
| 7 | $n \le 10^5$，$a_i \le 10^{12}$ |
| 8 | |
| 9 | |
| 10 |
时间限制：$1\texttt{s}$
空间限制：$256\texttt{MB}$
鄂公网安备 42010202000505 号