CF1237C2.Balanced Removals (Harder)

This is a harder version of the problem. In this version, $n \le 50\,000$.

There are $n$ distinct points in three-dimensional space numbered from $1$ to $n$. The $i$-th point has coordinates $(x_i, y_i, z_i)$. The number of points $n$ is even.

You'd like to remove all $n$ points using a sequence of $\frac{n}{2}$ snaps. In one snap, you can remove any two points $a$ and $b$ that have not been removed yet and form a perfectly balanced pair. A pair of points $a$ and $b$ is perfectly balanced if no other point $c$ (that has not been removed yet) lies within the axis-aligned minimum bounding box of points $a$ and $b$.

Formally, point $c$ lies within the axis-aligned minimum bounding box of points $a$ and $b$ if and only if $\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)$, and $\min(z_a, z_b) \le z_c \le \max(z_a, z_b)$. Note that the bounding box might be degenerate.

Find a way to remove all points in $\frac{n}{2}$ snaps.

这是一个更难的版本。在此版本中，$n \le 50\,000$。

在三维空间中有 $n$ 个互不相同的点，编号从 $1$ 到 $n$。第 $i$ 个点的坐标为 $(x_i, y_i, z_i)$。点的总数 $n$ 是偶数。

你希望用 $\frac{n}{2}$ 次“点击”（snap）操作移除全部 $n$ 个点。每次点击操作中，你可以任选两个尚未被移除的点 $a$ 和 $b$ 并将其同时移除，前提是它们构成一个“完美平衡对”（perfectly balanced pair）。点对 $a$ 和 $b$ 被称为完美平衡对，当且仅当不存在其他尚未被移除的点 $c$ 位于点 $a$ 和 $b$ 的轴对齐最小包围盒（axis-aligned minimum bounding box）内部。

形式化地，点 $c$ 位于点 $a$ 和 $b$ 的轴对齐最小包围盒内部，当且仅当

$$\min(x_a, x_b) \le x_c \le \max(x_a, x_b),\quad \min(y_a, y_b) \le y_c \le \max(y_a, y_b),\quad \min(z_a, z_b) \le z_c \le \max(z_a, z_b).$$

注意：该包围盒可能退化（即某维长度为零）。

请找出一种方案，在 $\frac{n}{2}$ 次点击操作内移除所有点。

The first line contains a single integer $n$ ($2 \le n \le 50\,000$; $n$ is even), denoting the number of points.

Each of the next $n$ lines contains three integers $x_i$, $y_i$, $z_i$ ($-10^8 \le x_i, y_i, z_i \le 10^8$), denoting the coordinates of the $i$-th point.

No two points coincide.

第一行包含一个整数 $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$ 个点的坐标。

任意两个点均不重合。

Output $\frac{n}{2}$ pairs of integers $a_i, b_i$ ($1 \le a_i, b_i \le n$), denoting the indices of points removed on snap $i$. Every integer between $1$ and $n$, inclusive, must appear in your output exactly once.

We can show that it is always possible to remove all points. If there are many solutions, output any of them.

输出 $\frac{n}{2}$ 对整数 $a_i, b_i$（$1 \le a_i, b_i \le n$），表示第 $i$ 次“快照”（snap）中被移除的点的下标。$1$ 到 $n$（含端点）之间的每个整数在你的输出中必须恰好出现一次。

我们可以证明：总是存在一种方式将所有点全部移除。若存在多种解，输出任意一种即可。

In the first example, here is what points and their corresponding bounding boxes look like (drawn in two dimensions for simplicity, as all points lie on $z = 0$ plane). Note that order of removing matters: for example, points $5$ and $1$ don't form a perfectly balanced pair initially, but they do after point $3$ is removed.

在第一个示例中，下图展示了各点及其对应的边界框（为简化起见，在二维平面上绘制，因为所有点均位于 $z = 0$ 平面上）。注意：移除点的顺序至关重要。例如，点 $5$ 和点 $1$ 最初并不构成一个完全平衡的点对，但在点 $3$ 被移除后，它们便构成了一个完全平衡的点对。