题目描述

译自 POI 2012 Stage 1. 「Distance」

定义一次「操作」为将一个正整数除以或乘以一个质数。定义函数 $d(a, b)$ 表示将 $a$ 进行若干次“操作”变成 $b$ 所需要的最小操作次数。例如，$d(69, 42) = 3$。

$d$ 显然是一个距离函数，满足以下性质：

• $d(a, a) = 0$
• $d(a, b) = d(b, a)$
• $d(a, b) + d(b, c) \geq d(a, c)$

给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，对每个 $a_i (1 \leq i \leq n)$，求 $j$ 使得 $j \neq i$ 且 $d(a_i, a_j)$ 最小。如果有多个满足条件的 $j$，应输出最小的那个。

输入格式

第一行一个正整数 $n (2 \leq n \leq 100,000)$。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq 1,000,000)$。

输出格式

输出 $n$ 行，每行一个整数，表示使 $j \neq i$ 且 $d(a_i, a_j)$ 最小的 $j$。

样例

输入：

6
1
2
3
4
5
6

输出：

2
1
2
3
2
2

数据范围与提示

对于 30% 的数据有 $n \leq 1000$。

对于所有数据有 $2 \leq n \leq 10^5$, $1 \leq a_i \leq 10^6$。