A hillside vineyard is modeled as a binary tree of vines. Diagonals run down the slope: the root is on diagonal 0, a right-child edge stays on the same diagonal, and a left-child edge steps to the next diagonal (so a node's diagonal index equals the count of left-child edges from the root to it). List the vines one diagonal at a time, starting from diagonal 0. Within a single diagonal, list the nodes in the order they are reached by a level-order (breadth-first, left-to-right) traversal of the whole tree.
Input format
Line 1: an integer n, the number of tokens on the next line.
Line 2: n space-separated tokens describing a binary tree in level-order (breadth-first). The first token is the root's value. Reading left to right, keep a queue of already-created nodes; for each node taken from the front of the queue, the next two tokens are its left child then its right child, where the token null marks a missing child. Only non-null children are added to the queue. Trailing null tokens for absent children at the deepest level may be omitted. Every node value is an integer.
Output format
A single line: node values grouped by diagonal (from 0 upward), each diagonal's nodes in level-order, all space-separated.
Constraints
- 1 <= n <= 129
- The tree has at least 1 and at most 40 nodes.
- Each node value is an integer with -1000 <= value <= 1000.