D. Черно-белое дерево
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

На доске нарисован граф-дерево из n вершин. Напомним, что неориентированный граф называется деревом, если он связен и не содержит циклов.

Каждая вершина графа покрашена в черный или белый цвет таким образом, что не существует двух вершин одного цвета, соединенных ребром. На каждом ребре записана его стоимость — неотрицательное целое число.

Плохой мальчик Вася подошел к доске и написал около каждой вершины v число sv — сумму стоимостей всех инцидентных этой вершине ребер, после чего он стер ребра и их стоимости с доски.

Ваша задача — восстановить исходное дерево по цветам вершин и числам sv.

Входные данные

В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 105) — количество вершин в дереве. Далее в n строках записаны пары разделенных пробелом целых чисел ci, si (0 ≤ ci ≤ 1, 0 ≤ si ≤ 109), где ci означает цвет i-ой вершины (0 — белый, 1 — черный), а si означает сумму стоимостей инцидентных i-ой вершине ребер в нарисованном на доске дереве.

Выходные данные

Выведите описание n - 1 ребер графа-дерева. Каждое описание — это тройка чисел vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109), где vi и ui — номера вершин, которые соединяет i-ое ребро, а wi — его стоимость. Обратите внимание, что должно выполняться условие cvi ≠ cui.

Гарантируется, что для любых входных данных существует по крайней мере один соответствующий этим данным граф. Если существует несколько решений, то выведите любое. Ребра разрешается выводить в любом порядке. Числа при выводе разделяйте пробелами.

Примеры
Входные данные
3
1 3
1 2
0 5
Выходные данные
3 1 3
3 2 2
Входные данные
6
1 0
0 3
1 8
0 2
0 3
0 0
Выходные данные
2 3 3
5 3 3
4 3 2
1 6 0
2 1 0