Contruct a rooted tree using N nodes which is rooted at node 1, such that the value of the given function Z is maximized.
i-Nj-N
z= [F(i,j)] where F(i, j) = (S(i, j) ALCA(i, j)]) + (S(i, j) × A[LCA(i, j)])
a
·
i-1 ji+1
@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≤ N ≤ 500
1≤ Ai≤ 1000000000
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.
SAMPLE INPUT
3
4 1 9
3 4
SAMPLE OUTPUT
1 2
2 3