这是问题的更难版本。在此版本中,$$$n \le 50\,000$$$。
三维空间中有 $$$n$$$ 个不同的点,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i, z_i)$$$。点数 $$$n$$$ 是偶数。
您想要使用一系列 $$$\frac{n}{2}$$$ 捕捉来删除所有 $$$n$$$ 点。只需轻轻一击,您就可以删除尚未删除的任意两个点 $$$a$$$ 和 $$$b$$$,并形成完美平衡的一对。如果没有其他点 $$$c$$$(尚未删除)位于点 $$$a$$$ 和 $$$b$$$ 的轴对齐最小边界框内,则一对点 $$$a$$$ 和 $$$b$$$ 完美平衡。
形式上,点 $$$c$$$ 位于点 $$$a$$$ 和 $$$b$$$ 的轴对齐最小边界框内当且仅当 $$$\min(x_a, x_b) \le x_c \le \max(x_a, x_b)$$$, $$$\min(y_a, y_b) \le y_c \le \max(y_a, y_b)$$$ 和 $$$\min(z_a, z_b) \le z_c \le \max(z_a, z_b)$$$。请注意,边界框可能会退化。
找到一种方法来删除 $$$\frac{n}{2}$$$ 快照中的所有点。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50\,000$$$;$$$n$$$ 为偶数),表示点数。
接下来的 $$$n$$$ 行包含三个整数 $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$-10^8 \le x_i, y_i, z_i \le 10^8$$$),表示第 $$$i$$$ 个点的坐标。
没有两点重合。
输出
输出 $$$\frac{n}{2}$$$ 整数对 $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$),表示在快照 $$$i$$$ 上删除的点的索引。 $$$1$$$ 和 $$$n$$$(含)之间的每个整数必须在输出中恰好出现一次。
我们可以证明总是可以删除所有点。如果有多个解,则输出任意一个。
示例
输入 #1
6 3 1 0 0 3 0 2 2 0 1 0 0 1 3 0 0 1 0
输出 #1
3 6 5 1 2 4
输入 #2
8 0 1 1 1 0 1 1 1 0 1 1 1 2 2 2 3 2 2 2 3 2 2 2 3
输出 #2
4 5 1 6 2 7 3 8
注意
在第一个示例中,点及其相应的边界框如下所示(为简单起见,以二维绘制,因为所有点都位于 $$$z = 0$$$ 平面上)。请注意删除的顺序很重要:例如,点 $$$5$$$ 和 $$$1$$$ 最初并不形成完美平衡的对,但在点 $$$3$$$ 被删除后它们就会形成完美平衡的对。