Zigzag Level Order Traversal

Traverse a binary tree level by level, but alternate the direction on each level: the first level left-to-right, the second right-to-left, and so on.

Input Format

The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null).

Output Format

Print each level on its own line (in the zigzag direction), values separated by single spaces. Print nothing for an empty tree.