찬솔이 构造了一棵有 $N$ 个节点、每个节点上写有整数的二叉搜索树。二叉搜索树是一棵二叉树，对于每个节点 $i$，$i$ 的左子树中所有节点上的数都小于 $i$ 上的数，$i$ 的右子树中所有节点上的数都大于 $i$ 上的数。

찬솔이 记录了所有 $i$ 的二叉搜索树中节点 $i$ 的深度 $H_i$ 以及节点 $i$ 上的整数 $A_i$。其中，所有 $A_i$ 互不相同，且根节点的深度为 $1$。（$1 \le i \le N$）

찬솔이 在参加 ICPC World Finals 期间丢失了这棵二叉搜索树。请帮助 찬솔이 利用之前记录的信息恢复这棵二叉搜索树。

输入格式

第一行给出节点个数 $N$。($1 \leq N \leq 200\,000$)

接下来 $N$ 行，每行给出树的节点信息。对于所有 $1 \leq i \leq N$，第 $(i+1)$ 行包含节点 $i$ 上的整数 $A_i$ 和节点 $i$ 的深度 $H_i$，以空格分隔。($-2\cdot 10^9\leq A_i \leq 2\cdot 10^9$；$1 \leq H_i \leq N$) 所有 $A_i$ 互不相同。

输出格式

如果无法根据给定的记录恢复二叉搜索树，则输出 $-1$。

如果可以恢复，则输出 $N$ 行表示树的结构。

第 $i$ 行输出节点 $i$ 的左孩子和右孩子的节点编号。如果没有孩子，则输出 $-1$ 作为孩子编号。

如果存在多种可能的树，输出任意一种即可。

样例

输入格式 1

3
1 2
2 1
3 2

输出格式 1

-1 -1
1 3
-1 -1

输入格式 2

3
1 1
2 2
3 2

输出格式 2

-1

输入格式 3

3
2 2
5 3
4 2

输出格式 3

-1

输入格式 4

3
100 2
200 1
300 2

输出格式 4

-1 -1
1 3
-1 -1