A complete binary tree is made of nodes arranged in a
hierarchic structure. One of the nodes is the root node, said
to be at level 0. The root node has two child nodes, which are
at level 1. Each of those has two children at level 2 etc.
In general, a complete binary tree with $N$ levels has $2^ N - 1$ nodes, each of which has
two child nodes, except those at level $N - 1$.
A number can be written into each node. Write the numbers
$1$ to $2^ N - 1$ into a complete binary tree
with $N$ levels so that,
for each node at level $D$, the absolute value of the
difference of the sum of all numbers in the left subtree and
the sum of all numbers in the right subtree is $2^ D$.
For example, the sum of the left subtree of the root node
must differ from the sum of the right subtree by 1. The sums of
the left and right subtrees of a node at level 1 must differ by
2. Each number must be used exactly once. The solution need not
The first and only line of input contains the integer
$N (1 \le N \le 15)$, the
number of levels in the tree.
Output the $2^ N - 1$
separated by spaces on a single line, the binary tree in the
preorder traversal. The preorder traversal first outputs the
number in the root node, then outputs the left subtree (again
in the preorder traversal), then the right subtree.
|Sample Input 1
||Sample Output 1
1 2 3
|Sample Input 2
||Sample Output 2
1 3 4 6 2 5 7