Background

Let $\gcd(x,y)$ denote the greatest common divisor of $x$ and $y$, and let $\operatorname{lca}(x,y)$ denote the lowest common ancestor of node $x$ and node $y$.

Problem Description

You are given $n$ nodes, numbered $1,2,\ldots,n$, with weights $a_1,a_2,\ldots,a_n$.

Please use these $n$ nodes to construct a tree such that for all $1 \le i < j \le n$, $\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$.

If there is no solution, report it. Otherwise, output the shape of the tree.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \ldots , a_n$.

Output Format

If there is no solution, output -1.

Otherwise, output one line with $n$ integers. The $i$-th number denotes the parent index of node $i$. In particular, if node $i$ is the root, output 0.

If there are multiple solutions, output any one of them.

5
1 2 3 4 5

0 1 1 2 1

5
1 2 3 4 6

-1

Hint

【Constraints and Notes】

This problem uses bundled testdata.

• Subtask 1 (5 points): $n = 2$.
• Subtask 2 (5 points): all $a_i$ are equal.
• Subtask 3 (5 points): $n \le 5$.
• Subtask 4 (10 points): a solution is guaranteed to exist.
• 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): no special restrictions.

For $100\%$ of the testdata, $2 \le n \le 10^5$ and $1 \le a_i \le 10^6$.

Translated by ChatGPT 5