A regional office keeps its reporting hierarchy as a binary tree of employee ids. The hierarchy is given in level-order (breadth-first) form as a single line of space-separated tokens, where the token null marks a missing child. The first token is the root; then, following the standard level-order layout, every non-null node contributes exactly two following tokens for its left and right child (each of which may itself be null, and null tokens never contribute further tokens of their own).
An auditor reads the hierarchy level by level, but alternates scanning direction on every level: level 0 (the root) is scanned left-to-right, level 1 is scanned right-to-left, level 2 left-to-right again, and so on, alternating forever.
Print every id in the exact order the auditor encounters them.
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null).
Output format
A single line: the node values in zigzag level order, space-separated. If the tree is empty (the input is just null), print an empty line.
Constraints
- 0 <= number of nodes <= 500
- Each node value is an integer with -1000 <= value <= 1000
- The input is a valid level-order encoding of some binary tree