Laikan Gift

Let a finite set S of positive integers be called good if and only if for any two elements x and y in S, the greatest common divisor \(\gcd(x,y)\) is also in S. Note that the empty set \(\varnothing\) is also considered good.

We define the Laikan order on good sets as follows. For two good sets \(A\) and \(B\), we say \(A < B\) if and only if at least one of the following conditions holds:

• \(\max A < \max B\);
• \(\max A = \max B\) and \(A \setminus \{\max A\} < B \setminus \{\max B\}\).

By convention, \(\max \varnothing = -\infty\). It turns out that, restricted to good sets, this ordering is well-defined.

You wish to gift a good set to your dear friend on the \(k\)th day of separation. To make the gift extra memorable, you sort all good sets (in ascending Laikan order) as an infinite sequence \(S_0, S_1, S_2, \ldots\), and you will give the set \(S_k\) to your friend. Your task is to determine the elements of the set \(S_k\>.

Observation: A nonempty good set \(S\) is exactly the set of all positive divisors of its maximum element. In other words, for \(k \ge 1\), \(S_k = D(k)\) where \(D(k)\) is the set of all divisors of \(k\). Note that \(S_0\) is the empty set.

inputFormat

The input consists of a single integer \(k\) \((0 \le k \le 10^6)\), representing the index of the good set you will gift.

outputFormat

If \(k = 0\), output an empty line (or no output). Otherwise, output the elements of \(S_k\) (i.e. all positive divisors of \(k\)) in increasing order, separated by a single space.

sample

0