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.*;

import java.io.*;

public class C {
	static ArrayList<Integer> primes;
	static int[] isComposite;
	static int[] idx;
	static int[] p;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		idx = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		int ix = 1;
		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				idx[i] = ix;
				ix++;
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
		p = new int[primes.size()];
		int i = 0;
		for (int x : primes) {
			p[i++] = x;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine());
		pair[] p = new pair[t];
		for (int i = 0; i < p.length; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			p[i] = new pair(a, b, c, i + 1);
		}
		Arrays.sort(p);
		ArrayList<pair1> rz = new ArrayList<>();
		ArrayList<pair2> ans = new ArrayList<pair2>();
		ans.add(new pair2(p[0].x, p[0].y, p[0].idx));
		int z = p[0].z;
		for (int i = 1; i <= t; i++) {
			while (i < p.length && p[i].z == z) {
				ans.add(new pair2(p[i].x, p[i].y, p[i].idx));
				i++;
			}
			Collections.sort(ans);
			ArrayList<pair1> ry = new ArrayList<>();
			ArrayList<pair1> a = new ArrayList<>();
			a.add(new pair1(ans.get(0).x, ans.get(0).idx));
			int y = ans.get(0).y;
			for (int j = 1; j <= ans.size(); j++) {
				while (j < ans.size() && ans.get(j).y == y) {
					a.add(new pair1(ans.get(j).x, ans.get(j).idx));
					j++;
				}
				Collections.sort(a);
				if (a.size() % 2 == 1)
					ry.add(a.get(a.size() - 1));
				for (int w = 0; w < a.size() - 1; w += 2) {
					pw.println(a.get(w).idx + " " + a.get(w + 1).idx);
				}
				if (j != ans.size()) {
					a = new ArrayList<>();
					a.add(new pair1(ans.get(j).x, ans.get(j).idx));
					y = ans.get(j).y;
				}
			}
			if (ry.size() % 2 == 1)
				rz.add(ry.get(ry.size() - 1));
			for (int w = 0; w < ry.size() - 1; w += 2) {
				pw.println(ry.get(w).idx + " " + ry.get(w + 1).idx);
			}
			if(i!=p.length) {
				z=p[i].z;
				ans=new ArrayList<>();
				ans.add(new pair2(p[i].x, p[i].y, p[i].idx));
			}
		}
		for (int i = 0; i < rz.size(); i += 2) {
			pw.println(rz.get(i).idx + " " + rz.get(i + 1).idx);
		}
		pw.flush();

	}

	static int g_div(int x) {
		for (int i = 2; i * i <= x; i++)
			if (x % i == 0)
				return x / i;
		return 1;
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;
		int z;
		int idx;

		public pair(int d, int u, int w, int in) {
			x = d;
			y = u;
			z = w;
			idx = in;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub

			return z - o.z;
		}

	}

	static class pair2 implements Comparable<pair2> {
		int x;
		int y;
		int idx;

		public pair2(int d, int u, int in) {
			x = d;
			y = u;
			idx = in;
		}

		@Override
		public int compareTo(pair2 o) {
			// TODO Auto-generated method stub
			return y - o.y;

		}

	}

	static class pair1 implements Comparable<pair1> {
		int x;
		int idx;

		public pair1(int d, int w) {
			x = d;
			idx = w;
		}

		@Override
		public int compareTo(pair1 o) {
			// TODO Auto-generated method stub

			return x - o.x;
		}

	}

}
