Background

xtq has an unusual talent for orienteering. In first grade, he won first place in the "Problem-Solving Cup" and also won the "Cricket Cup" "cricket". One day, he was studying a problem.

Problem Description

xtq wants to design a circular map, which can be seen as a circle. On the circumference, there are any number of non-overlapping checkpoints, and each checkpoint has some tasks.

Let all possible tasks form a $k$-element set. Then this set has $2^k$ distinct subsets, denoted as $A_1,A_2......A_{2^k}$. Each checkpoint has exactly one task subset among $A_1,A_2......A_{2^k}$. Note that different checkpoints may have the same task subset.

xtq wants to satisfy the following conditions:

$1$: For any subsets $Ai$, $Aj$ satisfying $||Ai|-|Aj||=1$, there exists exactly one pair of adjacent checkpoints whose task subsets are $Ai$ and $Aj$.

$2$: For any adjacent checkpoints with subsets $Ai$, $Aj$, it always holds that $||Ai|-|Aj||=1$.

Now xtq gives you an $n$, and he wants you to find all possible $2\le k\le n$ such that there exists at least one way to place checkpoints and assign tasks.

In the above description, $|Ai|$ denotes the number of elements in $|Ai|$, and $|a+b|$ denotes the absolute value of $a+b$.

Input Format

One positive integer $n$.

Output Format

Output several lines. Each line contains one positive integer, representing a possible $k$, in increasing order.

3

2

Hint

[Sample Explanation]

When $k=2$, suppose all possible tasks are $\{1,2\}$. Then the 4 subsets of tasks are $\emptyset$, $\{1\}$, $\{2\}$, $\{1,2\}$. The following figure shows one valid arrangement:

In the figure, $\{\emptyset\}$ should be $\emptyset$ (typo).

[Constraints]

For $50\%$ of the testdata, $n\le 5000$.

For $100\%$ of the testdata, $n$ fits in the range of $long long$, and $2\le n$.

Translated by ChatGPT 5