Problem: The board has got a painted tree graph, consisting of n nodes. Let us remind you that a non-directed graph is called a tree if it is connected and doesn't contain any cycles.

Each node of the graph is painted black or white in such a manner that there aren't two nodes of the same color, connected by an edge. Each edge contains its value written on it as a non-negative integer.

A bad boy Vasya came up to the board and wrote number sv near each node v — the sum of values of all edges that are incident to this node. Then Vasya removed the edges and their values from the board.

Your task is to restore the original tree by the node colors and numbers sv.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 105) — the number of nodes in the tree. Next n lines contain pairs of space-separated integers ci, si (0 ≤ ci ≤ 1, 0 ≤ si ≤ 109), where ci stands for the color of the i-th vertex (0 is for white, 1 is for black), and si represents the sum of values of the edges that are incident to the i-th vertex of the tree that is painted on the board.

Output

Print the description of n - 1 edges of the tree graph. Each description is a group of three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109), where vi and ui — are the numbers of the nodes that are connected by the i-th edge, and wi is its value. Note that the following condition must fulfill cvi ≠ cui.

It is guaranteed that for any input data there exists at least one graph that meets these data. If there are multiple solutions, print any of them. You are allowed to print the edges in any order. As you print the numbers, separate them with spaces.

Examples

Input

3
1 3
1 2
0 5


Output

3 1 3
3 2 2


Input

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


Output

2 3 3
5 3 3
4 3 2
1 6 0
2 1 0

Solution (in JAVA):

Solution:

import com.sun.org.apache.bcel.internal.classfile.InnerClass;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeSet;

/**
 * 4 6
 * 1 2
 * 1 3
 * 1 4
 * 2 3
 * 2 4
 * 3 4
 *
 *
 *
 *
 *
 *
 * @author pttrung
 */
public class D {

    public static void main(String[] args) {
        Scanner in = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File("output.txt")));
        int n = in.nextInt();
        TreeSet<Node> black = new TreeSet();
        TreeSet<Node> white = new TreeSet();

        ArrayList<Node>[] map = new ArrayList[n];
        boolean[] hold = new boolean[n];
        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList();

            int b = in.nextInt();
            if (b == 1) {
                hold[i] = true;
                black.add(new Node(i, b, in.nextInt()));
            } else {
                white.add(new Node(i, b, in.nextInt()));
            }
        }
        int lastB = 0, lastW = 0;
        while (!black.isEmpty() && !white.isEmpty()) {
            Node b = black.pollFirst();
            Node w = white.pollFirst();
            lastB = b.index;
            lastW = w.index;
            if (b.num > w.num) {
                out.println((b.index + 1) + " " + (w.index + 1) + " " + w.num);

                b.num -= w.num;
                w.num = 0;
            } else {
                out.println((b.index + 1) + " " + (w.index + 1) + " " + b.num);

                w.num -= b.num;
                b.num = 0;
            }
            map[b.index].add(w);
            map[w.index].add(b);
            if (w.num != 0) {
                white.add(w);
            }
            if (b.num != 0) {
                black.add(b);
            }
        }

        boolean[] check = new boolean[n];
        dfs(lastB, -1, map, check);
        for (int i = 0; i < n; i++) {
            if (!check[i]) {
                if (!hold[i]) {
                    out.println((lastB + 1) + " " + (i + 1) + " " + 0);
                } else {
                    out.println((lastW + 1) + " " + (i + 1) + " " + 0);
                }
                dfs(i, -1, map, check);
            }
        }
        out.close();
    }

    public static void dfs(int node, int pa, ArrayList<Node>[] map, boolean[] check) {
        check[node] = true;
        for (Node n : map[node]) {
            if (n.index != pa) {
                dfs(n.index, node, map, check);
            }
        }
    }

    public static class Node implements Comparable<Node> {

        int index, black, num;

        public Node(int index, int black, int num) {
            this.index = index;
            this.black = black;
            this.num = num;
        }

        @Override
        public int compareTo(Node o) {
            if (num != o.num) {
                return num - o.num;
            } else {
                return index - o.index;
            }
        }
    }

    public static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        public void update(int index, int value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public int get(int index) {
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

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

    public static long pow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return val * val;
        } else {
            return val * (val * a);
        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

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

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

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

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}