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.

既然海蒂已经知道她可以将反抗军的宇宙飞船分配给基地（回忆一下简单子任务），她现在向你提问：具体该如何操作？现在，给定平面上 $N$ 艘宇宙飞船和 $N$ 个基地的位置，你的任务是用线段将宇宙飞船与基地连接起来，使得：

• 这些线段互不相交；
• 这样的连接构成一个完美匹配。

The first line contains an integer N (1 ≤ n ≤ 10000). For 1 ≤ i ≤ N, the i + 1-th line contains two integers x__i and y__i (|x__i|, |y__i| ≤ 10000) denoting the coordinates of the i-th spaceship. The following N lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and no three points are on the same line.

第一行包含一个整数 $N$（$1 \leq N \leq 10000$）。对于 $1 \leq i \leq N$，第 $i+1$ 行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10000$），表示第 $i$ 艘飞船的坐标。接下来的 $N$ 行格式相同，表示基地的位置。保证任意两点不重合，且任意三点不共线。

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.

输出应包含 N 行。第 i 行应包含一个整数 p__i，表示第 i 艘飞船所连接的基地的编号。序列 _p_1, ..., p__N 应构成 1, ..., N 的一个排列。

保证存在解。若存在多个解，输出其中任意一个即可。