Balancing Sums in a Complete Binary Tree

Given a complete binary tree with n levels (the root is at level \(0\), its children at level \(1\), and so on), assign the numbers \(1,2,\dots,2^n-1\) (each used exactly once) to the nodes of the tree such that for every internal node at level \(d\) (i.e. a node which has both left and right subtrees), the absolute difference between the sum of the numbers in its left subtree and the sum of the numbers in its right subtree is exactly \(2^d\).

Your task is to output any one valid assignment in the preorder traversal order. (Note that for a leaf, no condition is required.)

Remark: A complete binary tree with n levels has \(2^n-1\) nodes. The level of a node (when numbering starts at 0 for the root) is defined as \(\lfloor\log_2(i)\rfloor\) if the node is stored in an array starting at index 1.

In this problem, you need to find one assignment of the numbers to the nodes satisfying the condition and then output the numbers in the order of preorder traversal (i.e. root → left subtree → right subtree).

inputFormat

The input consists of a single integer n (n ≥ 1) indicating the number of levels in the complete binary tree.

outputFormat

Output the valid assignment (a permutation of \(1,2,\dots,2^n-1\)) in one line representing the preorder traversal of the tree. The numbers should be separated by a single space.

sample

1

1