题目描述

定义 $\operatorname{sgcd}(x,y)$ 表示 $x,y$ 的次大公因数，即能同时整除 $x,y$ 的正整数中第二大的数。

特别的，若不存在次大公因数则定义 $\operatorname{sgcd}(x,y)=-1$。

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，求出 $\operatorname{sgcd}(a_1,a_1),\operatorname{sgcd}(a_1,a_2),\dots,\operatorname{sgcd}(a_1,a_n)$。

输入格式

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

第二行 $n$ 个由空格隔开的正整数，第 $i$ 个正整数表示 $a_i$。

输出格式

一行 $n$ 个由空格隔开的数，第 $i$ 个表示 $\operatorname{sgcd}(a_1,a_i)$。

4
12450 1 2 450

6225 -1 1 75

8
30030 6 10 12 55 36 450 666

15015 3 5 3 11 3 15 3

大样例

大样例

数据规模与约定