Chansol construyó un árbol binario de búsqueda con $N$ nodos, cada uno con un número entero. Un árbol binario de búsqueda es un árbol binario en el que, para cada nodo $i$, todos los números en los nodos del subárbol izquierdo de $i$ son menores que el número en $i$, y todos los números en los nodos del subárbol derecho de $i$ son mayores que el número en $i$.

Chansol registró, para cada $i$, la profundidad $H_i$ del nodo $i$ en el árbol binario de búsqueda y el entero $A_i$ escrito en el nodo $i$. Todos los $A_i$ son distintos y la profundidad del nodo raíz es $1$. ($1 \le i \le N$)

Chansol perdió el árbol binario de búsqueda mientras asistía a la ICPC World Finals. Ayuda a Chansol a reconstruir el árbol binario de búsqueda utilizando la información registrada anteriormente.

Entrada

La primera línea contiene el número de nodos $N$ ($1 \leq N \leq 200\,000$).

Las siguientes $N$ líneas contienen la información de los nodos del árbol. Para cada $1 \leq i \leq N$, la línea $(i+1)$-ésima contiene el entero $A_i$ escrito en el nodo $i$ y la profundidad $H_i$ del nodo $i$, separados por un espacio ($-2\cdot 10^9 \leq A_i \leq 2\cdot 10^9$; $1 \leq H_i \leq N$). Todos los $A_i$ son distintos.

Salida

Si no se puede reconstruir el árbol de búsqueda binaria a partir de los registros dados, imprime $-1$.

Si se puede reconstruir, imprime la estructura del árbol en $N$ líneas.

En la $i$-ésima línea, imprime los números de nodo del hijo izquierdo y del hijo derecho del nodo $i$. Si un hijo no existe, imprime $-1$ como el número de ese hijo.

Si hay múltiples árboles que se pueden reconstruir, cualquiera es aceptable.

Ejemplos

Entrada 1

3
1 2
2 1
3 2

Salida 1

-1 -1
1 3
-1 -1

Entrada 2

3
1 1
2 2
3 2

Salida 2

-1

Entrada 3

3
2 2
5 3
4 2

Salida 3

-1

Entrada 4

3
100 2
200 1
300 2

Salida 4

-1 -1
1 3
-1 -1