Вам дано пару чисел \((a_i, b_i)\) і необхідно побудувати декартове дерево, таке що \(i\)-а вершина має ключі \((a_i, b_i)\), вершини з ключем \(a_i\) утворюють бінарне дерево пошуку, а вершини з ключем \(b_i\) утворюють купу.

Формат вхідних даних

У першому рядку записано кількість \(N\) - кількість пар.

Далі слідує \(N\) (\(1 \leq N \leq 50\,000\)) пар \((a_i, b_i)\). Для всіх пар \(\lvert a_i\rvert, \lvert b_i \rvert \leq 30\,000\). \(a_i \neq a_j\) і \(b_i \neq b_j\) для всіх \(i \neq j\).

Формат вихідних даних

Якщо декартове дерево з таким набором ключів побудувати можливо, виведіть у першому рядку \(YES\), інакше виведіть \(NO\).

У разі відповіді \(YES\), виведіть \(N\) рядків, кожен з яких повинен описувати вершину. Опис вершини складається з 3-х чисел: номер предка, номер лівого сина та номер правого сина. Якщо у вершини відсутній предок або якийсь із синів, то виводьте на його місці число \(0\).

Якщо підходящих дерев декілька, то виведіть будь-яке.

Приклад вхідних даних

7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

Приклад вихідних даних

YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0