29139번 - Дерево 스페셜 저지다국어

문제

Недавно на уроке информатики Саша узнала о двоичных деревьях поиска.

Двоичным деревом поиска называется двоичное дерево, в каждой вершине которого написано число, называемое ключом этой вершины. Причем ключ, записанный в вершине, больше всех ключей, записанных в левом поддереве этой вершины, но меньше всех ключей, записанных в ее правом поддереве.

Такая организация чисел позволяет эффективно реализовать структуру данных <<множество чисел>>. То есть мы можем построить двоичное дерево поиска по некоторому множеству чисел, а потом эффективно проверять, принадлежит ли то или иное число этому множеству.

Саша уже реализовала двоичное дерево поиска. Но вдруг она поняла, что хранить множество чисел --- не очень интересно. Намного интереснее хранить структуру данных, представляющую собой так называемый <<ассоциативный массив>>. Это такая структура данных, в которой для каждого ключа хранится некоторое другое число, называемое значением этого ключа. То есть, в каждой вершине дерева находится по два числа --- ключ и значение, причем это дерево является двоичным деревом поиска по ключам вершин.

Так как Саша уже реализовала двоичное дерево поиска, то она хочет придумать такую структуру ассоциативного массива, при которой ей пришлось бы хранить в вершине только одно число.

Определим такую операцию над двоичным деревом поиска, хранящим пары ключ-значение: Новым ключом левого сына данной вершины становится ключ данной вершины, а новым ключом ее правого сына --- ее значение. Если у вершины до выполнения операции не было левого или правого сына, то он появляется и получает соответствующий ключ. Новым ключом корня становится некоторое число $ T $.

Вам дано двоичное дерево поиска, но не даны значения, хранящиеся в вершинах. Выведите любой подходящий набор таких значений (где каждое число целое и лежит в диапазоне от $ 1 $ до $ 10^9 $) при которых дерево, полученное операцией, описанной выше, будет являться деревом поиска. Или определите, что это невозможно.

입력

В первой строке входного файла через пробел даны два числа $ n $ и $ T $ ($ 1 \le n \le 10^5 ,ドル $ 1 \le T \le 10^9 $) --- количество вершин в исходном дереве и ключ корня в новом дереве.

В следующих $ n $ строках перечислена информация о вершинах. На $i$-ой строке находятся три числа $ l_i ,ドル $ r_i ,ドル $ a_i $ ($ 1 \le l_i \le n ,ドル $ 0 \le r_i \le n ,ドル $ 0 \le a_i \le 10^9 $) --- номер вершины, являющейся левым потомком вершины $ i ,ドル номер вершины, являющейся ее правым потомком и ключ этой вершины. Если у вершины нет какого-то потомка, то вместо соответствующего числа в файле записан 0. Первая вершина является корнем дерева.

출력

Если решения не существует, то в первой строке выходного файла выведите -1. Иначе, выведите $ n $ чисел --- для каждой вершины выведите значение в ней. Каждое число должно быть целым и лежать в диапазоне от $ 1 $ до $ 10^9 $

제한

힌트