During a short break in a hot battle against Kappel's corps, Petka and
Chapaev brought boxes with cartridges for the Anka's Maxim gun.
The Red Army men were exhausted because they had carried more than one
box with cartridges to the machine gun, and each box contained at least
one hundred cartridges. Anka noticed that there was the same number of
cartridges in all boxes.
She wanted to put all the cartridges in several pockets so that the
greatest common divisor of the numbers of cartridges in her pockets
would be as large as possible. Among all the variants of such an
arrangement, she wanted to choose the variant in which the least common
multiple of the numbers of cartridges in her pockets would be as
large as possible too. How could she do it?
The only input line contains the total number n of cartridges
Petka and Chapaev brought (200 ≤ n ≤ 109).
The only output line should contain integers a1, a2, …, ak
separated with a space (2 ≤ k ≤ n), where ai is the number of
cartridges Anka should put in the ith pocket.
If there are several answers, output any of them.
Problem Author: Daniil Ayzenshteyn (idea by Alex Samsonov)
Problem Source: NEERC 2010, Eastern subregional contest