Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Given a set of \(N\) nodes, where each node has an integer \(A[i]\) associated with it.

Construct a rooted tree using \(N\) nodes which is rooted at node \(1\), such that the value of the given function \(Z\) is maximized.

\(Z = \sum_\limits{i = 1}^{i = N} [\sum_\limits{j = i + 1}^{j = N}[F(i,j)]]\) where \(F(i,j) = (S(i,j) \ \oplus \ A[LCA(i,j)]) + (S(i,j) \ \times \ A[LCA(i,j)])\)

\(\oplus\) denotes the bitwise xor operator.
\(S(i, j)\) denotes the number of edges on the simple path between nodes i and j.
\(LCA(i,j)\) denotes the lowest common ancestor of nodes i and j.

Input format

First line contains an integer N denoting number of nodes in the tree.
Next line contains N space separated integers denoting the value of each node i.e. A[i].

Output format

Print N - 1 lines where each line contains
- Two space separated integers a b denoting an edge between node a and b in the tree.

Constraints

\(2 \le N \le 500 \\ 1 \le A[i] \le 10^9\)

Verdit and Scoring

\(Z\) is the score for each test case.
If the output is not a tree or contains any invalid entry, then you will receive a Wrong Answer verdict.