Usually, people are accustomed to arranging all $n$-bit binary strings in lexicographical order. For example, all 2-bit binary strings in lexicographical order are: 00, 01, 10, 11.

A Gray code is a special arrangement of $n$-bit binary strings where any two adjacent strings differ by exactly one bit. Specifically, the first string and the last string are also considered adjacent.

Let $c_i$ denote the number of times the $i$-th bit is the one that differs between two adjacent strings.

An example of a 2-bit Gray code arrangement is: 00, 01, 11, 10. The corresponding $c$ sequence is: $c_1=2$, $c_2=2$.

There is more than one $n$-bit Gray code. You want to find one that minimizes the range (the difference between the maximum and minimum values) of the $c$ sequence. If there are multiple such answers, output any one of them.

Input

A single positive integer $n$, as described in the problem statement.

Output

A single line containing $2^n$ positive integers. For all $1 \le i < 2^n$, the $i$-th integer represents the bit position that differs between the $i$-th and $(i+1)$-th binary strings in your construction. The $2^n$-th integer represents the bit position that differs between the first and the last string.

Examples

Input 1

2

Output 1

1 2 1 2

Input 2

3

Output 2

1 3 1 2 1 3 1 2

Constraints

This problem uses a custom checker (Special Judge) for evaluation.

There are 25 test cases in total, each worth the same amount of points. The $T$-th test case satisfies $n = T$.

For each test case, the scoring is as follows:

• If your output is an $n$-bit Gray code and the range of the $c$ sequence is minimized, you receive 100% of the points for that test case.
• If your output is an $n$-bit Gray code but the range of the $c$ sequence is not minimized, you receive 20% of the points for that test case.
• Otherwise, you receive 0% of the points.

Note

The output data for this problem is large; please use efficient output methods.