Tree

Sasha recently learned about binary search trees in her computer science class. A binary search tree is a binary tree where each vertex holds a number called its key. The key of a vertex is greater than every key in its left subtree and less than every key in its right subtree.

Such a tree lets you store a set of numbers and check efficiently whether a given number belongs to the set. Sasha has already implemented a binary search tree. Storing a set is not very interesting to her, though. She would rather store an associative array, where each key has another number called its value. Each vertex then holds two numbers, a key and a value, and the tree is a binary search tree by the vertex keys.

Sasha wants an associative array design in which each vertex stores only one number. She defines the following operation on a binary search tree that stores key-value pairs. The new key of the left child of a vertex becomes the key of that vertex. The new key of the right child becomes the value of that vertex. If a vertex has no left or right child before the operation, that child appears and gets the corresponding key. The new key of the root becomes some number $T$.

You are given a binary search tree, but the values stored in its vertices are not given. Print any set of values, where each value is an integer from $1$ to $10^9$, such that the tree obtained after the operation is a binary search tree. If no such set exists, print that it is impossible.

The first line contains two integers $n$ and $T$ separated by a space ($1 \le n \le 10^5$, $1 \le T \le 10^9$), where $n$ is the number of vertices in the original tree and $T$ is the key of the root in the new tree.

The next $n$ lines describe the vertices. Line $i$ contains three integers $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$): the index of the left child of vertex $i$, the index of its right child, and the key of vertex $i$. If a vertex has no left or right child, the corresponding number is 0. The first vertex is the root of the tree.

If no solution exists, print $-1$ on the first line. Otherwise, print $n$ numbers, the value of each vertex in order. Each number must be an integer from $1$ to $10^9$.