Great Akbardin decided to build new roads in his caliphate. He wants to build minimal number of roads so that one can travel from any town to any other using only these roads. But this problem is too difficult for him and his mathematicians. So, at first, they decided to build straight roads between towns in such a way, that every town becomes connected with only one other. Because crossroads make movement dangerous, no two roads should intersect.
You task is to make plan of the roads being given coordinates of towns.
Input
First line contains an even integer N (N ≤ 10000) — the number of towns. Each of the next N lines contains pair of integers — coordinates of i-th town xi, yi (−109 < xi, yi < 109).
No three towns lay on one line.
Output
Output N/2 lines with description of one road on each. Road is identified by pair of towns it connects. If there are several correct answers, output any of them.
Sample
input | output |
---|
4
0 2
1 1
3 4
4 4
| 1 3
2 4
|
Problem Author: Pavel Atnashev
Problem Source: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002