Balanced Removals (Harder)
Contest: Codeforces Global Round 5
Difficulty rating: 1900
Tags: binary search, constructive algorithms, divide and conquer, greedy, implementation, sortings

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0

Example output:
3 6
5 1
2 4

Example input:
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

Example output:
4 5
1 6
2 7
3 8

Editorial:
Consider a one-dimensional version of the problem where $$$n$$$ is not necessarily even. We can sort all points by their $$$x$$$-coordinate and remove them in pairs. This way, we'll leave at most one point unremoved.
Now, consider a two-dimensional version of the problem where $$$n$$$ is not necessarily even. For each $$$y$$$, consider all points that have this $$$y$$$-coordinate and solve the one-dimensional version on them. After we do this, we'll have at most one point on each $$$y$$$ left. Now we can sort the points by $$$y$$$ and remove them in pairs in this order. Again, we'll leave at most one point unremoved.
Finally, consider a three-dimensional version of the problem. Again, for each $$$z$$$, consider all points that have this $$$z$$$-coordinate and solve the two-dimensional version on them. After we do this, we'll have at most one point on each $$$z$$$ left. Now we can sort the points by $$$z$$$ and remove them in pairs in this order.
We can even generalize this solution to any number of dimensions and solve the problem in $$$O(dn \log n)$$$.