Restoring the Complete Binary Tree

Given a complete binary tree with \(2^K-1\) nodes, the tree was traversed according to the following rules:

• The traversal starts at the unique node on the first level (the root).
• If the current node's left child has not yet been recorded, record the left child's value and move to the left child.
• If the current node does not have a left child or its left child has been recorded, then record the current node's value.
• If the current node has already been recorded, record its right child's value and move to the right child.
• If the current node and its two children have all been recorded, then move back to the parent node.

The recorded sequence is exactly the in-order traversal of the tree. Given this sequence, reconstruct the original complete binary tree. Since the structure of a complete binary tree is uniquely determined by its number of nodes, you can recover the tree by noticing that the root is the middle element of the in-order sequence, and then the left and right subtrees are formed by the left and right halves of the sequence respectively.

After reconstruction, output the tree level by level. For each level, print the node values (separated by a single space) in order from left to right.

inputFormat

The input begins with an integer K (denoting the number of levels in the complete binary tree).
Following that is a line containing \(2^K-1\) integers separated by spaces, which represent the recorded in-order traversal of the tree.

Constraints:
1 ≤ K ≤ 10

outputFormat

Output the reconstructed complete binary tree in level order. Each level should be printed on a separate line, where the nodes in that level are separated by a single space.

sample

2
2 1 3

1
2 3