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.