Given a non-negative integer matrix of size . For a tree with vertices, numbered from to , we call it a if and only if:
For any pair of vertices and (), equals the bitwise XOR sum of the indices of the vertices on the simple path from to in the tree.
Your task is to construct a holly tree. It is guaranteed that such a holly tree always exists.
输入格式
The first line of the input contains an integer (), which is the size of matrix .
The next lines of the input describe the matrix . The -th line contains integers (). Note that holds for all .
It is guaranteed that such a holly tree always exists.
输出格式
Output lines, each containing two integers and (), representing an edge of the holly tree.
样例
样例输入 1
2
1 3
2
样例输出 1
1 2
样例输入 2
4
1 3 2 5
2 0 7
3 6
4
样例输出 2
1 2
1 3
1 4
样例输入 3
6
1 7 4 5 2 3
2 1 6 7 0
3 5 4 3
4 3 2
5 5
6
样例输出 3
4 1
2 3
6 4
5 2
4 2
数据范围与提示
In the second example, the tree in the output is shown in the following figure:
:::align{center}
:::
This tree is a holly tree. For example, for the pair of vertices , the simple path from to includes vertices , and , with a bitwise XOR sum of , which satisfies the constraint given in the input.
:::