# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# And... Yet Another AND Problem

By YouKnowWho · Limits 1s, 512 MB

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

InputOutput
1

1 0

InputOutput
2

3 1 0 2

InputOutput
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.

### Statistics

71% Solution Ratio

Noshin_1703086Earliest, 1w ago

Hotash_MeyeFastest, 0.0s

Noshin_1703086Lightest, 131 kB

FrdhsnShortest, 356B