Chansol zbudował binarne drzewo poszukiwań (BST) składające się z $N$ węzłów, w których zapisane są liczby całkowite. Binarne drzewo poszukiwań to takie drzewo binarne, że dla każdego węzła $i$ wszystkie liczby w lewym poddrzewie węzła $i$ są mniejsze od liczby w węźle $i$, a wszystkie liczby w prawym poddrzewie węzła $i$ są większe od liczby w węźle $i$.

Chansol zapisał dla każdego $i$ głębokość $H_i$ węzła $i$ w drzewie oraz liczbę całkowitą $A_i$ znajdującą się w węźle $i$. Wszystkie $A_i$ są różne, a głębokość korzenia wynosi $1$. ($1 \le i \le N$)

Podczas podróży na ICPC World Finals Chansol zgubił drzewo. Pomóż mu odtworzyć binarne drzewo poszukiwań na podstawie wcześniej zapisanych informacji.

Wejście

Pierwszy wiersz zawiera liczbę węzłów $N$. ($1 \leq N \leq 200\,000$)

Kolejne $N$ wierszy zawiera informacje o węzłach drzewa. Dla każdego $1 \leq i \leq N$, $(i+1)$-szy wiersz zawiera liczbę całkowitą $A_i$ zapisaną w węźle $i$ oraz głębokość $H_i$ węzła $i$, oddzielone spacją. ($-2\cdot 10^9\leq A_i \leq 2\cdot 10^9$; $1 \leq H_i \leq N$) Wszystkie $A_i$ są różne.

Wyjście

Jeżeli na podstawie podanych danych nie można odtworzyć binarnego drzewa poszukiwań, wypisz $-1$.

W przeciwnym przypadku wypisz strukturę drzewa w $N$ wierszach.

W $i$-tym wierszu wypisz numery lewego i prawego dziecka węzła $i$. Jeżeli dziecko nie istnieje, wypisz $-1$ jako numer dziecka.

Jeżeli istnieje wiele możliwych drzew, możesz wypisać dowolne z nich.

Przykład

Wejście 1

3
1 2
2 1
3 2

Wyjście 1

-1 -1
1 3
-1 -1

Wejście 2

3
1 1
2 2
3 2

Wyjście 2

-1

Wejście 3

3
2 2
5 3
4 2

Wyjście 3

-1

Wejście 4

3
100 2
200 1
300 2

Wyjście 4

-1 -1
1 3
-1 -1