Description

You are given a complete binary tree with $2^K-1$ nodes. The traversal rule of this tree is as follows:

• The starting point is the only node on the first level of the binary tree.

• If the left child of the current node has not been recorded yet, record the label of the left child and move to the left child.

• If the current node has no left child, or its left child has already been recorded, record the label of the current node.

• If the current node has already been recorded, record the label of the right child and move to the right child.

• If the current node and both its left and right children have all been recorded, move to the parent of the current node.

Now, you are given the sequence of labels recorded starting from the node on the first level. Please reconstruct the original complete binary tree.

Input Format

The first line contains an integer $K$, meaning that this complete binary tree has $2^K-1$ nodes.

The second line contains $2^K-1$ integers, representing the sequence of labels recorded starting from the node on the first level.

Output Format

Output $K$ lines in total, representing the original complete binary tree.

2
2 1 3 

1
2 3 

3
1 6 4 3 5 2 7

3
6 2
1 4 5 7

Hint

Sample Explanation #1

First move to node $1$. Seeing that the left child has not been recorded, move to node $2$ and record node $2$. Then, since node $2$ has no children, return to node $1$. Seeing that this node has not been recorded, record node $1$. Then, seeing that the right child has not been recorded, move to node $3$ and record node $3$.

Sample Explanation #2

Constraints

For $100\%$ of the testdata, $1\le K\le 10$.

Notes

The score of this problem follows the original COCI settings. The full score is $80$.

This problem is translated from COCI2013_2014 CONTEST #5 T2 OBILAZAK.

Translated by ChatGPT 5