1237_C2. Balanced Removals (Harder)_28560
This is a harder version of the problem. In this version, n ≤ 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 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) ≤ x_c ≤ max(x_a, x_b), min(y_a, y_b) ≤ y_c ≤ max(y_a, y_b), and min(z_a, z_b) ≤ z_c ≤ max(z_a, z_b). Note that the bounding box might be degenerate. 

Find a way to remove all points in n/2 snaps.

Input

The first line contains a single integer n (2 ≤ n ≤ 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 ≤ x_i, y_i, z_i ≤ 10^8), denoting the coordinates of the i-th point.

No two points coincide.

Output

Output n/2 pairs of integers a_i, b_i (1 ≤ a_i, b_i ≤ 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.

Examples

Input


6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0


Output


3 6
5 1
2 4


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


Output


4 5
1 6
2 7
3 8

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. 

<image>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		Point[] points = new Point[n];
		for (int i = 0; i < points.length; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int z = sc.nextInt();

			points[i] = new Point(x, y, z);
		}
		System.out.println(solve(points));

		sc.close();
	}

	static String solve(Point[] points) {
		Map<Point, Integer> pointToIndex = new HashMap<>();
		for (int i = 0; i < points.length; i++) {
			pointToIndex.put(points[i], i);
		}

		List<String> pairs = new ArrayList<>();
		Map<Integer, List<Point>> xToPoints = new HashMap<>();
		for (Point point : points) {
			if (!xToPoints.containsKey(point.x)) {
				xToPoints.put(point.x, new ArrayList<>());
			}

			xToPoints.get(point.x).add(point);
		}

		List<Point> remains = new ArrayList<>();
		for (List<Point> pointList : xToPoints.values()) {
			if (pointList.size() > 1) {
				pointList = removeBasedOnY(pairs, pointToIndex, pointList);
			}

			if (pointList.size() == 1) {
				remains.add(pointList.get(0));
			}
		}
		Collections.sort(remains, (p1, p2) -> Integer.compare(p1.x, p2.x));

		for (int i = 0; i < remains.size(); i += 2) {
			pairs.add(buildPair(pointToIndex, remains.get(i), remains.get(i + 1)));
		}

		return String.join("\n", pairs);
	}

	static List<Point> removeBasedOnY(List<String> pairs, Map<Point, Integer> pointToIndex, List<Point> pointList) {
		Map<Integer, List<Point>> yToPoints = new HashMap<>();
		for (Point point : pointList) {
			if (!yToPoints.containsKey(point.y)) {
				yToPoints.put(point.y, new ArrayList<>());
			}

			yToPoints.get(point.y).add(point);
		}

		List<Point> remains = new ArrayList<>();
		for (List<Point> points : yToPoints.values()) {
			if (points.size() > 1) {
				points = removeBasedOnZ(pairs, pointToIndex, points);
			}

			if (points.size() == 1) {
				remains.add(points.get(0));
			}
		}
		Collections.sort(remains, (p1, p2) -> Integer.compare(p1.y, p2.y));

		for (int i = 0;; i += 2) {
			if (i == remains.size()) {
				return Collections.emptyList();
			}
			if (i + 1 == remains.size()) {
				return Arrays.asList(remains.get(i));
			}

			pairs.add(buildPair(pointToIndex, remains.get(i), remains.get(i + 1)));
		}
	}

	static List<Point> removeBasedOnZ(List<String> pairs, Map<Point, Integer> pointToIndex, List<Point> pointList) {
		Collections.sort(pointList, (p1, p2) -> Integer.compare(p1.z, p2.z));

		for (int i = 0;; i += 2) {
			if (i == pointList.size()) {
				return Collections.emptyList();
			}
			if (i + 1 == pointList.size()) {
				return Arrays.asList(pointList.get(i));
			}

			pairs.add(buildPair(pointToIndex, pointList.get(i), pointList.get(i + 1)));
		}
	}

	static String buildPair(Map<Point, Integer> pointToIndex, Point p1, Point p2) {
		return String.format("%d %d", pointToIndex.get(p1) + 1, pointToIndex.get(p2) + 1);
	}
}

class Point {
	int x;
	int y;
	int z;

	Point(int x, int y, int z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}

	@Override
	public int hashCode() {
		return Objects.hash(x, y, z);
	}

	@Override
	public boolean equals(Object obj) {
		Point other = (Point) obj;
		return x == other.x && y == other.y && z == other.z;
	}
}
6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0
 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
 4
-42939263 80157803 90523514
-42939263 94977529 90523514
-42939263 94977529 -3280468
-42939263 80157803 -3280468
 2
34319950 -11299623 -19866275
34319950 -11299623 98728529
 2
100000000 -100000000 -100000000
-100000000 -100000000 -100000000
 2
-100000000 -100000000 -100000000
-100000000 -100000000 100000000
 4
-53055455 42895224 28613596
-53061404 42895224 39577025
-53061404 42895224 28613596
-53055455 42895224 39577025
 2
-100000000 100000000 -100000000
-100000000 -100000000 -100000000
 2
-100000000 -100000000 -100000000
100000000 -100000000 -100000000
 2
35627406 -93449884 80249079
52771770 -93449884 80249079
 6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0
 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
-32839949 -68986721 41592956
-32839949 -31435211 41592956
 8
-100000000 -100000000 -100000000
100000000 100000000 100000000
-100000000 100000000 100000000
-100000000 -100000000 100000000
100000000 100000000 -100000000
100000000 -100000000 -100000000
-100000000 100000000 -100000000
100000000 -100000000 100000000
 2
62887961 73879338 -68804433
62887961 63665147 -68804433
 4
32117556 7831842 -38931866
32117556 -42244261 -38931866
-24487444 -42244261 -38931866
-24487444 7831842 -38931866
 4
-42939263 80157803 90523514
-42939263 94977529 64247458
-42939263 94977529 -3280468
-42939263 80157803 -3280468
 2
34319950 -11299623 -19866275
34319950 -222228 98728529
 2
100000000 -100000000 -100000000
-100000000 -100000000 -171045861
 6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 2 0
 8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 4 3
 8
-100000000 -100000000 -100000000
100000000 100001000 100000000
-100000000 100000000 100000000
-100000000 -100000000 100000000
100000000 100000000 -100000000
100000000 -100000000 -100000000
-100000000 100000000 -100000000
100000000 -100000000 100000000
 4
32117556 4239882 -38931866
32117556 -42244261 -38931866
-24487444 -42244261 -38931866
-24487444 7831842 -38931866
 8
0 1 2
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3
 4
-42939263 101881696 90523514
-42939263 94977529 64247458
-42939263 94977529 -3280468
-42939263 80157803 -3280468
 6
0 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 2 0
 8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
3 3 2
2 4 3
 6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 -1
1 1 0
 6
0 1 0
0 3 0
2 2 0
1 0 0
1 3 0
1 2 0
 4
-42939263 101881696 90523514
-42939263 94977529 64247458
-42939263 94977529 -460572
-8336053 80157803 -3280468
 6
0 1 0
0 3 0
0 2 0
1 0 0
1 3 0
1 2 0
 4
32117556 4239882 -38931866
32117556 -42244261 -46020877
-24487444 -42244261 -38931866
-5751467 7831842 -45745935
 6
0 1 0
0 3 0
0 4 0
1 0 0
1 3 0
1 2 0
 2
-100000000 -100000000 -100000000
-100000000 -66583883 100000000
 2
-100000000 100000000 -100000000
-100000000 -100000000 -164816150
 2
-65652541 -100000000 -100000000
100000000 -100000000 -100000000
 2
15781034 -93449884 80249079
52771770 -93449884 80249079
 2
-32839949 -68986721 68917885
-32839949 -31435211 41592956
 2
62887961 73879338 -68804433
26919603 63665147 -68804433
 6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 -1
0 1 0
 2
34319950 -11299623 -19866275
34319950 -222228 134477576
 2
100000010 -100000000 -100000000
-100000000 -100000000 -171045861
 2
-165691664 -100000000 -100000000
-100000000 -66583883 100000000
 2
-100000000 100000010 -100000000
-100000000 -100000000 -164816150
 2
-65652541 -100000000 -100000000
100000000 -100000000 -42390165
 2
15781034 -93449884 20051959
52771770 -93449884 80249079
 2
-32839949 -68986721 68917885
-25790425 -31435211 41592956
 2
62887961 131512713 -68804433
26919603 63665147 -68804433
 4
32117556 4239882 -38931866
32117556 -42244261 -46020877
-24487444 -42244261 -38931866
-24487444 7831842 -38931866
 8
0 1 2
1 0 0
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3
 4
-42939263 101881696 90523514
-42939263 94977529 64247458
-42939263 94977529 -460572
-42939263 80157803 -3280468
 2
34319950 -11299623 -19866275
9150889 -222228 134477576
 2
100000010 -100000000 -100000000
-100000000 -100000000 -158924809
 2
-165691664 -100000000 -100000000
-100000000 -66583883 000000000
 2
-100000000 100000010 -100000000
-100000000 -100000000 -137953987
 2
-65652541 -68402136 -100000000
100000000 -100000000 -42390165
 2
15781034 -76909018 20051959
52771770 -93449884 80249079
 8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
3 3 2
2 4 4
 2
-32839949 -68986721 67205973
-25790425 -31435211 41592956
 2
62887961 131512713 -68804433
26919603 65468611 -68804433
 4
32117556 4239882 -38931866
32117556 -42244261 -46020877
-24487444 -42244261 -38931866
-24487444 7831842 -45745935
 6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 -2
1 1 0
 8
-1 1 2
1 0 0
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3
 2
34319950 -11299623 -19866275
9150889 -115081 134477576
 2
100000010 -100000000 -100000000
-100000000 -100000000 -221918514
 2
-165691664 -3693680 -100000000
-100000000 -66583883 000000000
 2
-100000000 100000010 -100000000
-100000000 -100000000 -72974119
 2
-65652541 -68402136 -100000000
100100000 -100000000 -42390165
 2
15781034 -76909018 20051959
3025109 -93449884 80249079
 8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
5 2 2
3 3 2
2 4 4
 2
-32839949 -68986721 75726443
-25790425 -31435211 41592956
 2
62887961 131512713 -4892751
26919603 65468611 -68804433
 8
-1 1 2
1 0 0
1 1 0
1 1 1
2 2 2
5 2 2
2 3 2
2 2 3
 4
-42939263 101881696 90523514
-42939263 94977529 44705189
-42939263 94977529 -460572
-8336053 80157803 -3280468
 2
34319950 -11299623 -19866275
9150889 -115081 14346061
 2
100000010 -100000000 -100000000
-100000000 -100000000 -133957340
 2
-165691664 -3693680 -199581656
-100000000 -66583883 000000000
 2
-124067869 100000010 -100000000
-100000000 -100000000 -72974119
 2
-65652541 -68402136 -100000000
100100000 -100000000 -12856070
 2
15781034 -109253818 20051959
3025109 -93449884 80249079
 8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
8 2 2
3 3 2
2 4 4
 2
-32839949 -68986721 75726443
-25790425 -8936179 41592956
 2
62887961 131512713 -4892751
26919603 87621048 -68804433
 4
32117556 7140523 -38931866
32117556 -42244261 -46020877
-24487444 -42244261 -38931866
-5751467 7831842 -45745935
 4
-42939263 101881696 120845255
-42939263 94977529 44705189
-42939263 94977529 -460572
-8336053 80157803 -3280468
 2
34319950 -11299623 -19866275
9150889 -115081 18689305
 2
100000010 -100000000 -100000000
-5253442 -100000000 -133957340
 2
-165691664 -3693680 -199581656
-100000000 -66583883 001000000
 2
-124067869 100000010 -100000000
-100000000 -100000000 -143988809
 2
-65652541 -38723319 -100000000
100100000 -100000000 -12856070
 2
15781034 -109253818 20051959
3025109 -136507604 80249079
 6
0 1 0
0 5 0
0 4 0
1 0 0
1 3 0
1 2 0

6 2
4 5
3 1
 3 4
5 8
1 2
7 6
 4 1
3 2
 1 2
 2 1
 1 2
 3 2
1 4
 2 1
 1 2
 1 2
 6 2
4 5
3 1
 3 4
5 8
1 2
7 6
 1 2
 1 4
7 3
6 8
5 2
 2 1
 3 4
2 1
 4 1
3 2
 1 2
 2 1
 6 2
4 5
3 1
 3 4
5 7
1 2
8 6
 1 4
7 3
6 8
5 2
 3 4
2 1
 3 4
5 8
1 2
7 6
 3 2
4 1
 1 6
4 5
2 3
 3 4
5 8
6 7
1 2
 4 6
2 5
3 1
 1 2
4 6
5 3
 3 2
1 4
 1 3
4 6
2 5
 2 1
3 4
 1 2
4 6
3 5
 1 2
 2 1
 1 2
 1 2
 1 2
 2 1
 6 2
4 5
3 1
 1 2
 2 1
 1 2
 2 1
 1 2
 1 2
 1 2
 2 1
 3 4
2 1
 3 4
5 8
1 2
7 6
 3 2
4 1
 2 1
 2 1
 1 2
 2 1
 1 2
 1 2
 3 4
5 8
6 7
1 2
 1 2
 2 1
 3 4
2 1
 4 6
2 5
3 1
 3 4
5 8
1 2
7 6
 2 1
 2 1
 1 2
 2 1
 1 2
 2 1
 3 4
5 8
1 2
7 6
 1 2
 2 1
 3 4
5 8
1 2
7 6
 3 2
1 4
 2 1
 2 1
 1 2
 1 2
 1 2
 2 1
 3 4
5 8
1 2
7 6
 1 2
 2 1
 2 1
3 4
 3 2
1 4
 2 1
 2 1
 1 2
 1 2
 1 2
 2 1
 1 3
4 6
2 5
