COCI 2006/2007, Contest #4

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 2N−1 nodes, each of which has two child nodes, except those at level L−1.

A number can be written into each node. Write the numbers 1 to 2N−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 2D.

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 be unique.

Input

The first and only line of input contains the integer N (1 ≤ N ≤ 15), the number of levels in the tree.

Output

Output the 2N−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.

```2
```

```3 1 2
```

```3
```

Output

```3 1 7 5 6 2 4
```

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 32M

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (2/0)
I think the judge doesn't work correctly. Please check it!

• (3/3)
16:10: I previously said I wouldn't look into it. I think I actually will though; please give me a little bit.
16:17: I believe you are correct. I'll look into fixing it.

Thank you for your report. We previously did not have a custom judge for this problem, and the solutions were simply the results generated by the official solution. If you happened to write your output in the exact same way, then you got AC; otherwise, even if you had a correct solution, you got WA.

I wrote a custom judge for this problem, and I've rejudged some submissions. The following users now get AC for their correct solutions:
• duong211199
• klime
• mahdigh
• suchir
• Thomas_Orton

In addition, I found the following user to have cheated by copying the official solution verbatim. Accordingly, I've deleted said submission.
• branko_fu

For posterity, the following users happened to produce output in the exact same order as the official submission. I briefly reviewed their code and could not determine any obvious signs of cheating.