And... Yet Another AND Problem

YouKn0wWho has an integer $n$. He wants to find an integer sequence $a$ of size exactly $2n$ such that $0 \le a_i \lt 2^n$ for each valid $i$ and for each integer $k$ from $0$ to $2^n - 1$, there exists at least one non-empty subsequence of $a$ such that the bitwise AND of the elements of that subsequence is $k$.

Help YouKn0wWho find such a sequence. If there are multiple such sequences, output any. It can be shown that such a sequence always exists under the given constraints.

A sequence $b$ is a subsequence of a sequence $c$ if $b$ can be obtained from $c$ by deletion of several (possibly, zero or all) elements.

Input

The first and only line of the input will contain single integer $n \, (1 \le n \le 18)$.

Output

Output $2n$ integers $a_1, a_2, \ldots a_{2n}(0 \le a_i \lt 2^n)$ such that it satisfies the conditions mentioned in the statement. If there are multiple such sequences, output any.

Samples

Input	Output
1	1 0

Input	Output
2	3 1 0 2

Input	Output
3	4 3 5 6 7 1

In the third test case, you can achieve each integer from $0$ to $2^3-1=7$ as bitwise AND of the elements of some non-empty subsequence of $a$:

• $a_1 \mathbin{\&} a_3 \mathbin{\&} a_6 = 4 \mathbin{\&} 5 \mathbin{\&} 1 = 0$

• $a_6=1$

• $a_2 \mathbin{\&} a_4 \mathbin{\&} a_5 = 3 \mathbin{\&} 6 \mathbin{\&} 7 = 2$

• $a_2 = 3$

• $a_1 = 4$

• $a_3=5$

• $a_4 \mathbin{\&} a_5 = 6 \mathbin{\&} 7 = 6$

• $a_5 = 7$

Here, $\&$ is the bitwise AND operator.