Boundary Traversal of a Binary Tree

You are given a binary tree where each node is represented by three integers: x, y, and z. Here, x is the value of the node, while y and z denote the values of its left and right children respectively. A value of -1 indicates that the child does not exist.

The task is to perform a boundary traversal of the tree. The boundary traversal is defined as the sequence:

$$B(T)= \{root\} \cup L(T) \cup F(T) \cup R(T),$$

where:

• root is the root node of the tree.
• L(T) is the left boundary (excluding leaf nodes and the root), traversed top-down.
• F(T) are all the leaf nodes in left-to-right order.
• R(T) is the right boundary (excluding leaf nodes and the root), traversed bottom-up.

You need to construct the tree from the given input and then print the boundary traversal as a sequence of space-separated integers.

inputFormat

The first line contains an integer n denoting the number of nodes in the tree.

The following n lines each contain three space-separated integers: x y z.

• x is the value of the node.
• y is the value of its left child (or -1 if missing).
• z is the value of its right child (or -1 if missing).

outputFormat

Output a single line containing the boundary traversal of the binary tree. The node values should be printed as space-separated integers.

## sample

5
1 2 3
2 4 -1
4 -1 -1
3 -1 5
5 -1 -1

1 2 4 5 3