Spiral Level Order Traversal

You are given a binary tree and your task is to perform a spiral (zigzag) level order traversal. In a spiral traversal, the nodes at every level are visited alternately from left to right and then right to left.

The binary tree is provided in level order format, where the special token N indicates a missing (null) node.

Your goal is to output the spiral level order traversal as a sequence of integers separated by spaces.

The spiral order is defined as follows:

Consider the tree levels starting from the root (level 0). For even-indexed levels (0, 2, 4, ...), traverse the nodes from left to right; for odd-indexed levels (1, 3, 5, ...), traverse the nodes from right to left. The final output is the concatenation of nodes in each level in order.

For a formal definition, if the binary tree is given by its root node \( r \), then let \( L_0, L_1, L_2, \dots \) denote the levels of the tree. The spiral order \( S \) is defined as:

[ S = \begin{cases} L_0 \oplus \text{reverse}(L_1) \oplus L_2 \oplus \text{reverse}(L_3) \oplus \cdots \end{cases} ]

where \( \oplus \) represents concatenation and \( \text{reverse}(\cdot) \) reverses the order of nodes in that level.

inputFormat

The input consists of a single line, which contains a space-separated list of values representing the binary tree in level order. The token N represents a null node. For example:

1 2 3 4 5 6 7

represents a complete binary tree with 7 nodes, and

10 20 30 40 60 N 50

represents the tree where some nodes might be missing.

outputFormat

Output a single line with the nodes of the binary tree in spiral level order traversal. The values should be printed in a single line separated by a single space. If the tree is empty, output an empty line.

## sample

1 2 3 4 5 6 7

1 3 2 4 5 6 7

</p>