The school cafeteria at Gyeonggi Science High School is famous for its food, which is said to be comparable to that of a hotel restaurant. Pickle was waiting in the long line for lunch as usual. However, Jaewoo, one of the people standing behind Pickle, could not wait any longer and attempted to cut in line! Pickle does not tolerate anyone skipping their turn, so if Jaewoo is caught, he will be in serious trouble.

Before the line-cutting begins, there are $N$ people between Pickle and Jaewoo. The line-cutting occurs through the repetition of the following process:

When there are $n$ people between Pickle and Jaewoo, if Jaewoo attempts to skip $k$ people, Pickle will catch Jaewoo with a probability of $\frac{k}{n + 1}$. If Jaewoo is not caught in this attempt, the number of people between Jaewoo and Pickle decreases by $k$, becoming $n - k$ (where $1 \le k \le n$). If Jaewoo manages to skip $N$ people in total through $X$ attempts and ends up directly behind Pickle, Pickle will no longer notice Jaewoo's actions.

Since we want Jaewoo to be safe, we want to inform him of the method of cutting in line that minimizes the probability of being caught by Pickle. Therefore, we need to find and report the number of attempts to skip people and the number of people skipped in each attempt for the safest line-cutting method. If there are multiple answers, you may output any one of them.

Input

The number of people $N$ initially between Pickle and Jaewoo is given.

$1 \leq N \leq 10^5$

Output

On the first line, output the number of attempts $X$ when the probability of Jaewoo being caught by Pickle is minimized.

On the second line, output $X$ integers $k_1, k_2, \dots, k_X$ separated by spaces. Here, $k_i$ represents the number of people Jaewoo skipped in the $i$-th attempt. $(1 \le i \le X)$

Subtasks

1. $N \le 3$ (30 points)

2. $N \le 10$ (30 points)

3. No additional constraints. (40 points)

Examples

Input 1

4

Output 1

2
2 2