现在海蒂知道她可以将义军太空飞船分配给基地(回想一下简单的子任务),她问你:到底该怎么做?现在,给定平面上 N 艘宇宙飞船和 N 个基地的位置,你的任务是用线段连接宇宙飞船和基地,以便:
- 线段不相交。
- 这样的连接形成了完美的匹配。
输入
第一行包含一个整数 N (1 ≤ n ≤ 10000)。对于 1 ≤ i ≤ N,第 i + 1 行包含两个整数 xi 和 yi (|xi|, |yi| ≤ 10000),表示第 i 艘飞船的坐标。接下来的N行具有相同的格式,表示碱基的位置。保证没有两点重合,也没有三点在同一条直线上。
输出
输出应有 N 行。第 i 行应包含一个整数 pi,即第 i 艘飞船所连接的基座的索引。序列 p1, ..., pN 应形成 1, ..., N 的排列。
保证存在解。如果有多个解,可以输出其中任意一个。
示例
输入 #1
4 6 6 5 1 2 4 4 0 5 4 1 2 2 1 3 5
输出 #1
4 1 2 3