棋盘上有一个绘制的树形图,由 n 个节点组成。让我们提醒您,如果无向图是连通的且不包含任何环,则该图称为树。
图表的每个节点都被涂成黑色或白色,以确保不存在通过边连接的两个颜色相同的节点。每条边都包含以非负整数形式写在其上的值。
一个坏孩子 Vasya 走到黑板上,在每个节点 v 附近写下数字 sv — 与该节点相关的所有边的值的总和。然后 Vasya 从棋盘上删除边缘及其值。
你的任务是通过节点颜色和数字 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。
保证对于任何输入数据,至少存在一个满足这些数据的图。如果有多个解决方案,请打印其中任何一个。您可以按任何顺序打印边缘。打印数字时,用空格分隔它们。
示例
输入 #1
3 1 3 1 2 0 5
输出 #1
3 1 3 3 2 2
输入 #2
6 1 0 0 3 1 8 0 2 0 3 0 0
输出 #2
2 3 3 5 3 3 4 3 2 1 6 0 2 1 0