21131번 - Brilliant Sequence of Umbrellas 스페셜 저지다국어

문제

Anton has $n$ umbrellas, each of them has a different number from 1ドル$ to $n$ written on it. He wants to arrange some of the umbrellas in line so that they would form a brilliant sequence of umbrellas (BSU). A sequence of $k$ umbrellas with numbers $a_1, a_2, \ldots, a_k$ is considered a BSU if the following rules apply:

• $a_i > a_{i-1}$ for all 2ドル \le i \le k$;
• $\text{gcd}(a_i, a_{i-1}) > \text{gcd}(a_{i-1}, a_{i-2})$ for all 3ドル \le i \le k$. Here, $\text{gcd}(x, y)$ denotes the greatest common divisor of integers $x$ and $y$.

Anton would like to create a long BSU. Making the longest one doesn't bother him, he thinks that a BSU of length at least $\left\lceil\frac{2}{3}\sqrt{n}\right\rceil$ is quite enough.

Anton is busy reading fascinating books about lighthouses, so he asks you to find a BSU that would satisfy him.

입력

The only line contains an integer $n,ドル the number of umbrellas (1ドル \le n \le 10^{12}$).

출력

The first line should contain an integer $k,ドル the length of the BSU you have found ($\left\lceil\frac{2}{3}\sqrt{n}\right\rceil \le k \le 10^6$).

The second line should contain $k$ integers $a_i,ドル the sequence itself (1ドル \le a_i \le n$). The sequence should satisfy the rules mentioned above.

제한

힌트

In the first example, $\left\lceil \frac{2}{3} \cdot \sqrt{10} \right\rceil = 3,ドル $\text{gcd}(1, 2) = 1,ドル $\text{gcd}(2, 6) = 2$.

In the second example, $\left\lceil \frac{2}{3} \cdot \sqrt{22} \right\rceil = 4,ドル $\text{gcd}(1, 2) = 1,ドル $\text{gcd}(2, 6) = 2,ドル $\text{gcd}(6, 15) = 3$.