题目背景

规定 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数，$\operatorname{lca}(x,y)$ 表示 $x$ 号节点和 $y$ 号节点的最近公共祖先。

题目描述

给你 $n$ 个点，编号分别为 $1,2,\ldots,n$，点权分别为 $a_1,a_2,\ldots,a_n$。

请你用这 $n$ 个点构造一棵树，使得 $\forall 1 \le i < j \le n$，$\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$。

若无解，报告之，否则输出树的形态。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \ldots , a_n$。

输出格式

若无解，输出 -1;

否则输出一行 $n$ 个整数，第 $i$ 个数表示 $i$ 号节点的父节点编号。特别地，若 $i$ 号节点为根节点则输出 0。

若有多解，输出任意一解即可。

5
1 2 3 4 5

0 1 1 2 1

5
1 2 3 4 6

-1

提示

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（5 points）：$n = 2$。
• Subtask 2（5 points）：所有 $a_i$ 均相等。
• Subtask 3（5 points）：$n \le 5$。
• Subtask 4（10 points）：保证有解。
• Subtask 5（15 points）：$n \le 100$。
• Subtask 6（15 points）：$n \le 10^3$。
• Subtask 7（15 points）：$n \le 3 \times 10^3$。
• Subtask 8（30 points）：无特殊限制。

对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le a_i \le 10^6$。