Chansol created a binary search tree with $N$ nodes, each containing an integer. A binary search tree is a binary tree in which, for every node $i$, all integers in the left descendants of $i$ are smaller than the integer in $i$, and all integers in the right descendants of $i$ are larger than the integer in $i$.

For every $i$, Chansol recorded the depth $H_i$ of node $i$ in the binary search tree and the integer $A_i$ written on node $i$ of the binary search tree. All $A_i$ are distinct, and the depth of the root node is $1$. ($1 \le i \le N$)

Chansol lost the binary search tree while attending the ICPC World Finals. Using the previously recorded information, help Chansol reconstruct the binary search tree.

Input

The first line contains the number of nodes $N$. ($1 \leq N \leq 200\,000$)

The next $N$ lines contain the information of the tree nodes. For each $1 \leq i \leq N$, the $(i+1)$-th line contains the integer $A_i$ written on node $i$ and the depth $H_i$ of node $i$, separated by a space. ($-2\cdot 10^9 \leq A_i \leq 2\cdot 10^9$; $1 \leq H_i \leq N$) All $A_i$ are distinct.

Output

If the binary search tree cannot be reconstructed from the given records, output $-1$.

If it can be reconstructed, output the structure of the tree over $N$ lines.

The $i$-th line should contain the node numbers of the left child and the right child of node $i$. If a child does not exist, output $-1$ as the child's node number.

If there are multiple possible trees, any one can be output.

Examples

Input 1

3
1 2
2 1
3 2

Output 1

-1 -1
1 3
-1 -1

Input 2

3
1 1
2 2
3 2

Output 2

-1

Input 3

3
2 2
5 3
4 2

Output 3

-1

Input 4

3
100 2
200 1
300 2

Output 4

-1 -1
1 3
-1 -1