Description

E.Space had a dream.

He dreamed of a mysterious sequence. Someone told him that this sequence is closely related to tomorrow’s exam.

He decided to memorize this sequence. But after waking up, E.Space found that he did not remember the sequence, not even its length. However, he remembered that this sequence has a magical property.

In the dream, E.Space performed a series of operations on it. Let the sequence be $a_1, a_2, \dots, a_n$. Initially, it satisfies $\forall 1\le i\le n, a_i \ge 0$, and $a_n \neq 0$.

After that, in each operation, E.Space chooses an $i$ such that $a_i=i$, sets $a_i$ to $0$, and increases each of $a_1, a_2, \dots, a_{i-1}$ by $1$ from its original value.

E.Space remembers that after $n+k$ operations, this sequence becomes the all-zero sequence, i.e. $a_1=a_2=\cdots=a_n= 0$.

E.Space knows that there may be multiple sequences that satisfy this property, but he still hopes you can tell him one possible case, because maybe all sequences that satisfy this property could be useful in the exam.

His exam score is in your hands.

Input Format

One line contains one positive integer $k$.

Output Format

If you find a sequence that satisfies the property described by E.Space, output two lines.

The first line contains one positive integer $n$.

The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, where $a_n \neq 0$, representing this mysterious sequence.

If there are multiple possible mysterious sequences, output any one. If no such mysterious sequence exists, output one line Daydream! to tell E.Space that he is daydreaming.

1

2
1 2

5

4
1 2 2 4

Hint

Subtask $1$ (10 points): $k\le 6$.

Subtask $2$ (25 points): $k\le 10^6$.

Subtask $3$ (30 points): $k\le 10^{11}$. If a solution exists, it is guaranteed that there exists a solution satisfying $\forall 1\le i< n, a_i \neq i$.

Subtask $4$ (28 points): $k\le 10^{11}$.

Subtask $5$ (7 points): $k\le 10^{12}$.

Translated by ChatGPT 5