Complete Binary Tree

A complete binary tree has a layered structure. The root is on level 0, and the two children of the root are on level 1. In general, if a node is on level D, then each of its children is on level D + 1.

A complete binary tree of level N has all leaves on level N - 1, and it contains 2^N - 1 nodes in total. Every node whose level is not N - 1 has exactly one left child and one right child.

Write the integers from 1 through 2^N - 1 on the nodes, using every integer exactly once. For every internal node on level D, the absolute difference between the sum of the numbers in its left subtree and the sum of the numbers in its right subtree must be 2^D.

For example, at the root the two subtree sums must differ by 1, and at an internal node on level 1 they must differ by 2.

Given N, assign numbers to the nodes of the complete binary tree so that all conditions are satisfied, and print the result.

The first line contains the tree level N. (1 <= N <= 15)

Print, on one line, the preorder traversal of a complete binary tree whose nodes have been filled with numbers satisfying the conditions. If there are several valid answers, you may print any one of them.