チャンソルは、$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$)

2行目から $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