28316번 - The Filter 다국어

문제

Alice, the mathematician, likes to study real numbers that are between 0ドル$ and 1ドル$. Her favourite tool is the filter.

A filter covers part of the number line. When a number reaches a filter, two events can happen. If a number is not covered by the filter, the number will pass through. If a number is covered, the number will be removed.

Alice has infinitely many filters. Her first 3ドル$ filters look like this:

In general, the $k$-th filter can be defined as follows:

• Consider the number line from 0ドル$ to 1ドル$.
• Split this number line into 3ドル^k$ equal-sized pieces. There are 3ドル^k + 1$ points and 3ドル^k$ intervals.
• The $k$-th filter consists of the 2ドル^\text{nd}$ interval, 5ドル^\text{th}$ interval, 8ドル^\text{th}$ interval, and in general, the $(3i - 1)^\text{th}$ interval. The points are not part of the $k$-th filter.

Alice has instructions for constructing the Cantor set. Start with the number line from 0ドル$ to 1ドル$. Apply all filters on the number line, and remove the numbers that are covered. The remaining numbers form the Cantor set.

Alice wants to research the Cantor set, and she came to you for help. Given an integer $N,ドル Alice would like to know which fractions $\frac{x}{N}$ are in the Cantor set.

입력

The first line contains the integer $N$.

출력

Output all integers $x$ where 0ドル \le x \le N$ and $\frac{x}{N}$ is in the Cantor set.

Output the answers in increasing order. The number of answers will not exceed 10ドル^6$.

제한

• 2ドル \le N \le 10^9$

힌트