Problem Description

You are given a complete binary tree with a total of $n$ levels.

We label the root as being on level $0$. The two children of the root are on level $1$, and so on.

Now, we need to fill the $2^n - 1$ numbers from $1$ to $2^n - 1$ into the nodes, with no repetition and no omission, such that for any $d$, if we take a node on level $d$ as the root of a subtree, then the absolute value of the difference between the sum of numbers in its left subtree and the sum of numbers in its right subtree is equal to $2^d$.

Please output one feasible assignment. You only need to output the preorder traversal of this assignment.

Input Format

One line with one integer $n$, representing the number of levels of the tree.

Output Format

Output one line with $2^n - 1$ integers from $1$ to $2^n - 1$, separated by spaces, representing one possible preorder traversal.

If there are multiple answers, output any one of them. This problem uses SPJ.

2

3 1 2

3

3 1 7 5 6 2 4

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 15$.

Notes

This problem is translated from COCI2006-2007 CONTEST #4 T5 JOGURT.

Thanks to @一扶苏一 for providing the SPJ.

Translated by ChatGPT 5