Чансол построил двоичное дерево поиска из $N$ узлов, на каждом из которых записано целое число. Двоичное дерево поиска — это такое двоичное дерево, что для каждого узла $i$ все числа в узлах левого поддерева $i$ меньше числа, записанного в узле $i$, а все числа в узлах правого поддерева $i$ больше числа, записанного в узле $i$.

Для каждого $i$ Чансол записал глубину $H_i$ узла $i$ в двоичном дереве поиска и целое число $A_i$, записанное в узле $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)$-й строке через пробел заданы целое число $A_i$, записанное в узле $i$, и глубина $H_i$ узла $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