CF958E3 Guard Duty (hard)

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.

The first line contains an integer $ N $ ( $ 1

The output should have $ N $ lines. The $ i $ -th line should contain an integer $ p_{i} $ , the index of the base to which the $ i $ -th spaceship is connected. The sequence $ p_{1},...,p_{N} $ 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.