A binary tree of sensor ids is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children).
Define the boundary of the tree, read counter-clockwise starting at the root, as the concatenation of:
- the root's value;
- if the root is not a leaf: the values of every non-leaf node on the path obtained by starting at the root's left child and repeatedly moving to the left child if it exists, otherwise the right child, stopping before (i.e. not including) the first leaf reached on that path — this part is empty if the root has no left subtree or the very first node reached is already a leaf;
- the values of every leaf node in the whole tree, excluding the root, in left-to-right order;
- if the root is not a leaf: the values of every non-leaf node on the symmetric path starting at the root's right child (repeatedly moving right, else left, stopping before the first leaf), listed from the bottom of that path back up to the top (closest-to-a-leaf node first).
If the root itself is a leaf (including the single-node tree), the boundary is just the root's value. If the tree is empty, print an empty line.
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null).
Output format
A single line: the boundary values in the order defined above, space-separated (empty line if the tree is empty).
Constraints
- 0 <= number of nodes <= 300
- Each node value is an integer with -1000 <= value <= 1000