Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how exactly to do this? Now, given positions of N spaceships and N bases on a plane, your task is to connect spaceships and bases with line segments so that:
- The segments do not intersect.
- Such a connection forms a perfect matching.
Output
The output should have N lines. The i-th line should contain an integer pi, the index of the base to which the i-th spaceship is connected. The sequence p1, ..., pN should form a permutation of 1, ..., N.
It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 6
5 1
2 4
4 0
5 4
1 2
2 1
3 5
|
4
1
2
3
|