Constructing a GCD Conforming Tree

You are given n nodes numbered from 1 to n, and each node i is assigned a weight a_i. Your task is to construct a tree (a connected acyclic graph) using these n nodes such that for all pairs of nodes i and j (i < j), if l = lca(i,j) (the lowest common ancestor of i and j in the tree), then the following holds:

\(\gcd(a_i, a_j) = a_l\)

If no tree with this property exists, report that there is no solution; otherwise, output the structure of the tree. The tree should be output as a list of n-1 edges, each edge represented by the two endpoints (node numbers). In case there are multiple valid trees, output any one of them.

Notes and Hints:

• Since the tree is rooted (implicitly, by the LCA notion), an important observation is that for any edge from a parent v to a child u, it must hold that a_v divides a_u (because \(a_v = \gcd(a_v,a_u)\)).
• This divisibility condition forces a structure on the tree. In particular, one common strategy is to choose the node with the minimum weight, say m, as the root. Then, note that every other node must have a weight that is a multiple of m.
• A star tree with the minimum node as the center will satisfy the condition for every pair of nodes \(i,j\) (with lca(i,j)= the root) if, in addition, for every two other nodes \(i,j\), when writing a_i = m \times x and a_j = m \times y, we have \(\gcd(x,y) = 1\).
• If the star tree fails, another potential construction is a chain: sort the nodes in increasing order by weight and then connect them in a chain (i.e. for each consecutive pair, the smaller divides the larger). In such a chain, for any two nodes the lowest common ancestor is the one with the smaller weight – and by the chain property, the gcd of the two weights equals that smaller weight.
• If neither the star nor the chain construction is possible, then no valid tree exists; in that case, output -1.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes.

The second line contains n positive integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), where a_i denotes the weight of the i-th node.

outputFormat

If no valid tree exists, output -1 (without quotes). Otherwise, output n-1 lines; each line should contain two integers u and v indicating that there is an edge between nodes u and v in the tree. Any valid tree that satisfies the required property will be accepted.

For n = 1, output nothing.

sample

1
5