站外题求助

次大公约数

定义 sgcd(x,y) 表示 x 和 y 的次大公约数，即能同时整除x,y的正整数中第二大的数。如果次大公约数不存在，此时sgcd(x,y)=-1。

给定个数, 分别为 a1, a2, ..., an。求 sgcd(a1,a1), sgcd(a1,a2), ..., sgcd(a1,an)。

输入格式 第一行一个正整数 n。

第二行 n 个用空格隔开的正整数，第 i 个为 ai。

测试点 1~2 满足，n=1, ai<=10^9

测试点 3~6 满足，n = 10^4, ai <= 10^9

测试点7~10满足，n=10^5, ai <= 10^12

输出格式 一行 n 个用空格隔开的整数，第 i 个表示 sgcd(a1,ai)。

输入/输出例子1 输入：

4

12450 1 2 450

输出：

6225 -1 1 75

输入/输出例子2 输入：

8

30030 6 10 12 55 36 450 666

输出：

15015 3 5 3 11 3 15 3