We won't sing a sad third act, as the song says. That one is sad, admittedly; let's remember a cheerful one.
Do you know what šnenokle are? Šufnudle? Pihtije? Knaput?
Mr. Malnar knows, but he needs help with the following task:
Given an even natural number $N$. A set of numbers $S \subseteq \{0, 1, \dots, 2^N - 1\}$ is hungry if all $\binom{|S|}{2}$ bitwise XORs of pairs of elements from the set are distinct.
Find the largest possible hungry set.
Input
The only line of input contains a natural number $N$ from the problem description.
Output
In the first line, print the number of elements in your hungry set. In the second line, print the elements of the set separated by spaces.
Subtasks
| Subtask | $N$ | $t_1$ | $t_2$ | $t_3$ | Points |
|---|---|---|---|---|---|
| 1 | 18 | 267 | 283 | 512 | 20 |
| 2 | 20 | 444 | 462 | 1024 | 20 |
| 3 | 26 | 2019 | 2040 | 8192 | 20 |
| 4 | 28 | 3295 | 3327 | 16384 | 20 |
| 5 | 30 | 5377 | 5430 | 32768 | 20 |
If you output a hungry set of size $t$ for a subtask, your solution for that subtask will be scored according to the following expression:
$$ \text{points}(t) = \begin{cases} 2.4 \cdot \frac{t}{t_1} & t < t_1 \\ 2.4 + 3.6 \cdot \frac{t - t_1}{t_2 - t_1} & t_1 \le t < t_2 \\ 6 + 12 \cdot \frac{t - t_2}{t_3 - t_2} & t_2 \le t < t_3 \\ 20 & t_3 \le t \end{cases} $$
The points for each subtask will be rounded to two decimal places. The total number of points will correspond to the sum of points per subtask and will also be rounded to two decimal places.
Your source code can be at most 1 MiB.
Examples
Input 1
4
Output 1
6 0 1 2 4 8 15