Black and White Tree

给您一棵 $n$ 个节点的树，树边有边权，每个节点都有颜色，且只可能是黑色或白色（用 $0$ 或 $1$ 表示）。原树不存在树边连接 $2$ 个同色的节点。 现给出每个节点的颜色和与这个节点相连的边的权值和，请您还原这棵树。 ### 输入格式 第一行一个整数 $n$ ，节点数。 第 $2$ ~ $n+1$ 行，每行两个整数 $c_{i}$ , $s_{i}$ ，表示这个节点的颜色和与这个节点相连的边的权值和。 ### 输出格式 共输出 $n-1$ 行，每行 $u,v,w$ 代表这条边的左右端点和权值。

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 $ s_{v} $ 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 $ s_{v} $ .

The first line of the input contains a single integer $ n $ ( $ 2<=n<=10^{5} $ ) — the number of nodes in the tree. Next $ n $ lines contain pairs of space-separated integers $ c_{i} $ , $ s_{i} $ ( $ 0<=c_{i}<=1 $ , $ 0<=s_{i}<=10^{9} $ ), where $ c_{i} $ stands for the color of the $ i $ -th vertex (0 is for white, 1 is for black), and $ s_{i} $ 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.

Print the description of $ n-1 $ edges of the tree graph. Each description is a group of three integers $ v_{i} $ , $ u_{i} $ , $ w_{i} $ ( $ 1<=v_{i},u_{i}<=n $ , $ v_{i}≠u_{i} $ , $ 0<=w_{i}<=10^{9} $ ), where $ v_{i} $ and $ u_{i} $ — are the numbers of the nodes that are connected by the $ i $ -th edge, and $ w_{i} $ is its value. Note that the following condition must fulfill $ c_{vi}≠c_{ui} $ . 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.

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