ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC 2010, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Cartridges for Maxim

Time limit: 0.5 second
Memory limit: 64 MB
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?

Input

The only input line contains the total number n of cartridges Petka and Chapaev brought (200 ≤ n ≤ 109).

Output

The only output line should contain integers a1, a2, …, ak separated with a space (2 ≤ kn), where ai is the number of cartridges Anka should put in the ith pocket. If there are several answers, output any of them.

Samples

inputoutput
200
100 100
625
375 250 
Problem Author: Daniil Ayzenshteyn (idea by Alex Samsonov)
Problem Source: NEERC 2010, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1807. Cartridges for Maxim