Chansol a construit un arbre binaire de recherche de $N$ nœuds, chacun contenant un entier. Dans un arbre binaire de recherche, pour tout nœud $i$, tous les nombres écrits dans les nœuds du sous-arbre gauche de $i$ sont inférieurs au nombre écrit dans $i$, et tous les nombres écrits dans les nœuds du sous-arbre droit de $i$ sont supérieurs au nombre écrit dans $i$.

Chansol a noté, pour chaque $i$, la profondeur $H_i$ du nœud $i$ dans l'arbre binaire de recherche, ainsi que l'entier $A_i$ écrit sur ce nœud. Tous les $A_i$ sont distincts et la profondeur de la racine est $1$ ($1 \le i \le N$).

À son retour des finales mondiales de l'ICPC, Chansol a perdu son arbre binaire de recherche. Aidez-le à reconstruire l'arbre à l'aide des informations précédemment relevées.

Entrée

La première ligne contient le nombre de nœuds $N$ ($1 \leq N \leq 200\,000$).

Les $N$ lignes suivantes contiennent les informations des nœuds de l'arbre. Pour tout $1 \leq i \leq N$, la $(i+1)$-ième ligne contient l'entier $A_i$ écrit sur le nœud $i$ et la profondeur $H_i$ du nœud $i$, séparés par un espace ($-2\cdot 10^9\leq A_i \leq 2\cdot 10^9$ ; $1 \leq H_i \leq N$). Tous les $A_i$ sont distincts.

Sortie

S'il est impossible de reconstruire un arbre binaire de recherche à partir des données fournies, affichez $-1$.

Sinon, affichez la structure de l'arbre sur $N$ lignes.

La $i$-ième ligne doit contenir les numéros des fils gauche et droit du nœud $i$. Si un fils n'existe pas, affichez $-1$ comme numéro de ce fils.

S'il existe plusieurs arbres possibles, n'importe lequel peut être reconstruit.

Exemples

Entrée 1

3
1 2
2 1
3 2

Sortie 1

-1 -1
1 3
-1 -1

Entrée 2

3
1 1
2 2
3 2

Sortie 2

-1

Entrée 3

3
2 2
5 3
4 2

Sortie 3

-1

Entrée 4

3
100 2
200 1
300 2

Sortie 4

-1 -1
1 3
-1 -1