垃圾分类就是新时尚，早已化为每个市民的自觉行动，覆盖城乡的各个角落。垃圾分类又是一项大工程，分类投放、分类收运、分类处置，环环相扣，每一环都不可或缺。

但是没人比 P 王 Pmurt J. Dlanod 更懂垃圾分类。Pmurt 环卫公司开发了一种新型垃圾分类模式，马上会让人工智能生活垃圾分类 great again。我们称之为 Pmurt 模式。

垃圾处理厂每次收到一批“大杂烩”垃圾，会按顺序依次排开，从 $1$ 到 $N$ 编号。

首先，众所周知，AI 精确实别每一个垃圾的细分种类，是非常耗时（耗电）的。Pmurt 模式的系统的优越性在于，会对每个垃圾 $i$ 计算一个特征码 $a_i$。对于每个垃圾，我们需要找到它的最可能的“后续同类垃圾”。Pmurt 模式的“后续同类垃圾”是这样定义的：

• 对于每个 $i$，它的后续同类是 $\gcd(a_i,a_j)\ (i\lt j\le n)$ 中最大的 $j$ 号垃圾。（找不到默认是 $0$，如果有多个数具有相同最大的 $\gcd$，则选择最近的编号。）

注：$\gcd$ 是 Greatest Common Divisor，表示计算两个数的最大公约数。

现在你收到消息，P 王需要你在五点下班前实现这个功能，否则就要加班。也就是说，你需要实现一个程序，能够对每个输入的 $N$ 个垃圾，计算出它的“后续同类垃圾”。

第一行包含一个正整数 $N$，代表垃圾个数。

第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$，代表每个垃圾的特征值。

• $1 \le N \le 10^5$
• $1 \le a_i \le 2 \times 10^6$

输出一行，包含 $N$ 个整数，表示每个垃圾的后续同类垃圾的编号。

The 19th ZJNU Anniversary Contest