A factor-free tree is a rooted binary tree where every node in the tree contains a positive integer value that is coprime with all of the values of its ancestors. Two positive integers are coprime if their greatest common divisor equals .
The inorder sequence of a rooted binary tree can be generated recursively by traversing first the left subtree, then the root, then the right subtree. See Figure 1 below for the inorder sequence of one factor-free tree.
:::align{center}
:::
Figure 1: Illustration of Sample 1. The tree is factor-free; for example, the value of the node marked "" is coprime with all of the values of its ancestors, marked "", "", and "".
Given a sequence , decide if it is the inorder sequence of some factor-free tree and if so construct such a tree.
输入格式
The input consists of:
One line with one integer (), the length of the sequence.
One line with integers ( for each ), the elements of the sequence.
输出格式
If there exists a factor-free tree whose inorder sequence is the given sequence, output values. For each value in the sequence, give the -based index of its parent, or if it is the root. If there are multiple valid answers, print any one of them. If no such tree exists, output impossible instead.
:::