This is an easier version of the problem. In this version, n ≤ 2000.

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 ≤ 2000; 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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

import javafx.util.Pair;

public class Main {

    static long MOD = 0;
    static long[] fact = new long[1];
    static long[] x;
    static long[] y;
    static long[] z;

    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        int t = 1;
        while (t-- > 0) {
            solve();
        }
        long endTime = System.nanoTime();
        err.println("Execution Time : +" + (endTime - startTime) / 1000000 + " ms");
        exit(0);
    }

    static void solve() {
        int n = in.nextInt();
        x = new long[n];
        y = new long[n];
        z = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = in.nextLong();
            y[i] = in.nextLong();
            z[i] = in.nextLong();
        }
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; i++) {
            long d = Long.MAX_VALUE;
            if (used[i]) {
                continue;
            }
            int mindIndex = 0;
            for (int j = i + 1; j < n; j++) {
                if (used[j]) {
                    continue;
                }
                if (dist(i, j) < d) {
                    d = dist(i, j);
                    mindIndex = j;
                }
            }

            used[i] = true;
            used[mindIndex] = true;
            out.println((i + 1) + " " + (mindIndex + 1));

        }
    }

    static long dist(int i, int j) {
        return Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) + Math.abs(z[i] - z[j]);
    }

    static int valuesGreaterThan(ArrayList<Integer> d, int v) {
        int ind = Collections.binarySearch(d, v);
        if (ind < 0) {
            ind *= -1;
            ind--;
        } else {
            ind++;
        }
        return d.size() - ind;
    }

    static <T> Pair<T, T> make_pair(T a, T b) {
        return new Pair<>(a, b);
    }

    static class ModularArithmetic {
        static long C(int n, int k) {
            return divide(fact[n], mul(fact[k], fact[n - k]));
        }

        static void precalc(int N) {
            fact = new long[N + 5];
            fact[0] = 1;
            for (int i = 1; i < N; i++)
                fact[i] = mul(fact[i - 1], i);
        }

        static long inv(long x) {
            return mod_pow(x, MOD - 2);
        }

        static long mul(long x, long y) {
            return (x * y) % MOD;
        }

        static long divide(long x, long y) {
            return mul(x, inv(y));
        }

        static long add(long x, long y) {
            x += y;
            while (x >= MOD)
                x -= MOD;
            while (x < 0)
                x += MOD;
            return x;
        }

        static long mod_pow(long x, long y) {
            if (y == 0) {
                return 1;
            }
            if (y == 1) {
                return x;
            }
            long v = mod_pow(x, y / 2);
            if ((y & 1) > 0) {
                return v * v % MOD * x % MOD;
            }
            return v * v % MOD;
        }
    }

    static class StringUtils {
        static char[] constructReverseWithHash(String s) {
            char[] a = s.toCharArray();
            char[] b = ArrayUtils.reverse(s.toCharArray());
            char[] c = new char[a.length + b.length + 1];
            System.arraycopy(a, 0, c, 0, a.length);
            c[a.length] = '#';
            System.arraycopy(b, 0, c, a.length + 1, b.length);
            return c;
        }

        static String reverse(String s) {
            return constructStringFromChars(ArrayUtils.reverse(s.toCharArray()), 0, s.length());
        }

        static String constructStringFromChars(char[] d, int from, int to) {
            StringBuilder res = new StringBuilder();
            for (int i = from; i < to; i++) {
                res.append(d[i]);
            }
            return res.toString();
        }

        static String constructStringFromInts(int[] d, int from, int to) {
            StringBuilder res = new StringBuilder();
            for (int i = from; i < to; i++) {
                res.append(d[i]);
            }
            return res.toString();
        }

        static String constructStringFromInts(int[] d, int from, int to, char delim) {
            StringBuilder res = new StringBuilder();
            for (int i = from; i < to; i++) {
                res.append(d[i]);
                res.append(delim);
            }
            return res.toString();
        }

        static int[] prefix_function(char[] s) {
            int n = s.length;
            int[] pi = new int[n];
            for (int i = 1; i < n; i++) {
                int j = pi[i - 1];
                while (j > 0 && s[i] != s[j])
                    j = pi[j - 1];
                if (s[i] == s[j]) {
                    j++;
                }
                pi[i] = j;
            }
            return pi;
        }
    }

    static class NumberTheory {

        static ArrayList<Integer>[] getDivisors(int n) {
            ArrayList<Integer>[] d = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) {
                d[i] = new ArrayList<>();
            }
            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j += i) {
                    d[j].add(i);
                }
            }
            return d;
        }

        static long mod_pow(long x, long y, long MOD) {
            if (y == 0) {
                return 1;
            }
            if (y == 1) {
                return x;
            }
            long v = mod_pow(x, y / 2, MOD);
            if ((y & 1) > 0) {
                return v * v % MOD * x % MOD;
            }
            return v * v % MOD;
        }

        static int gcd(int a, int b) {
            while (b != 0) {
                int t = b;
                b = a % b;
                a = t;
            }
            return a;
        }

        //GCD Long
        static long gcd(long a, long b) {
            while (b != 0) {
                long t = b;
                b = a % b;
                a = t;
            }
            return a;
        }

    }

    static class ArrayUtils {

        static int[] reverse(int[] data) {
            int[] p = new int[data.length];
            for (int i = 0, j = data.length - 1; i < data.length; i++, j--) {
                p[i] = data[j];
            }
            return p;
        }

        static char[] reverse(char[] data) {
            char[] p = new char[data.length];
            for (int i = 0, j = data.length - 1; i < data.length; i++, j--) {
                p[i] = data[j];
            }
            return p;
        }

        static int[] MegreSort(int[] A) {
            if (A.length > 1) {
                int q = A.length / 2;
                int[] left = new int[q];
                int[] right = new int[A.length - q];
                System.arraycopy(A, 0, left, 0, q);
                System.arraycopy(A, q, right, 0, A.length - q);
                int[] left_sorted = MegreSort(left);
                int[] right_sorted = MegreSort(right);
                return Megre(left_sorted, right_sorted);
            } else {
                return A;
            }
        }

        static int[] Megre(int[] left, int[] right) {
            int[] A = new int[left.length + right.length];
            int i = 0;
            int j = 0;
            for (int k = 0; k < A.length; k++) {
                // To handle left becoming empty
                if (i == left.length && j < right.length) {
                    A[k] = right[j];
                    j++;
                    continue;
                }
                // To handle right becoming empty
                if (j == right.length && i < left.length) {
                    A[k] = left[i];
                    i++;
                    continue;
                }
                if (left[i] <= right[j]) {
                    A[k] = left[i];
                    i++;
                } else {
                    A[k] = right[j];
                    j++;
                }
            }
            return A;
        }

        static long[] MegreSort(long[] A) {
            if (A.length > 1) {
                int q = A.length / 2;
                long[] left = new long[q];
                long[] right = new long[A.length - q];
                System.arraycopy(A, 0, left, 0, q);
                System.arraycopy(A, q, right, 0, A.length - q);
                long[] left_sorted = MegreSort(left);
                long[] right_sorted = MegreSort(right);
                return Megre(left_sorted, right_sorted);
            } else {
                return A;
            }
        }

        static long[] Megre(long[] left, long[] right) {
            long[] A = new long[left.length + right.length];
            int i = 0;
            int j = 0;
            for (int k = 0; k < A.length; k++) {
                // To handle left becoming empty
                if (i == left.length && j < right.length) {
                    A[k] = right[j];
                    j++;
                    continue;
                }
                // To handle right becoming empty
                if (j == right.length && i < left.length) {
                    A[k] = left[i];
                    i++;
                    continue;
                }
                if (left[i] <= right[j]) {
                    A[k] = left[i];
                    i++;
                } else {
                    A[k] = right[j];
                    j++;
                }
            }
            return A;
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] readAllInts(int n) {
            int[] p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

        public int[] readAllInts(int n, int s) {
            int[] p = new int[n + s];
            for (int i = s; i < n + s; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static void exit(int a) {
        out.close();
        err.close();
        System.exit(a);
    }

    static InputStream inputStream = System.in;
    static OutputStream outputStream = System.out;
    static OutputStream errStream = System.err;
    static InputReader in = new InputReader(inputStream);
    static PrintWriter out = new PrintWriter(outputStream);
    static PrintWriter err = new PrintWriter(errStream);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

}
