Description

We use $|p|$ to denote the length of the sequence $p$.

Given an integer $m$, you are required to construct a sequence $a$ that satisfies:

• For all $1 \le i \le |a|$, $a_i \in [1, 10^6]$.
• There are exactly $m$ pairs $(i,j)$ such that $i<j$ and $a_i \mid a_j$.

You must ensure $2\le |a|\le 10^5$ and minimize the length of the sequence. It can be proven that there exists a sequence $a$ with the minimal length $|a|$ satisfying the conditions.

The special scoring rules are detailed in the data constraints.

Input Format

A single integer $m$ on a line.

Output Format

The first line outputs the length $n$ of the sequence. The second line outputs $n$ integers separated by spaces, representing the constructed sequence.

0

2
114 514

15

6
1 4 16 64 512 32768

Hint

For $100\%$ of the data, $0\le m\le 10^9$.

Subtask ID	$m$	Special Property	Score
$1$	$\le 9$	✗	$10$
$3$	$\le 170$	✓
$2$		✗	$20$
$4$	$\le 10^5$	^
$5$	Unrestricted	✓	$10$
$6$	^	✗	$30$

Special Property: There exists a positive integer $n$ such that

$$m=\frac{n(n-1)}{2}$$

Additionally, each test case has the following special scoring rule:

Let $s$ be the minimal possible length of $a$, and $l$ be the length of your sequence $a$. If the test case is worth $P$ points, you will obtain

$$\left\lfloor P\times \frac{\left\lfloor 100\cdot\left(\frac{s+114}{l+114}\right)^{1.14} \right\rfloor}{100} \right\rfloor$$

points. There may be minor differences due to precision issues.