시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 16 9 9 56.250%

문제

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.

예제 입력 1

10

예제 출력 1

3
1 2 6

예제 입력 2

22

예제 출력 2

4
1 2 6 15

힌트

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