Problem B. Beat the jocks ≡

 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

Statement

It is well known that high school students are usually divided into "nerds", who prefer to solve problems using their brains, and "jocks", who rely on their muscles instead. These groups often deride each other, each claiming their way is superior.

To determine which group is better at problem solving, teacher suggested the "locker challenge":

There is a corridor in the school with a row of N closed lockers. If you "toggled" the state of each locker (i.e. opening it if its closed, closing it if its open) in the following manner, which lockers would remain open?

• Every single locker is toggled (since all lockers start closed, this means each one is opened).
• Every other locker is toggled (in this case, closed), starting with the second.
• Every third locker is toggled, starting with the third.
• Every fourth locker is toggled, starting with the forth.
• ...
• The N-th locker is toggled.

The jocks would simply run along the corridor, opening and closing the lockers until they answered the question. Nerds try to work the solution out on paper. The first team to get the correct answer wins.

Since you are, hopefully, from the nerds camp, can you beat the jocks by writing the program which calculates the answer quickly enough?

Input file format

Input file contains integer N — the number of lockers.

Output file format

Output file must contain numbers of open lockers in increasing order.

1 ≤ N ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
1
2
5
1 4

0.212s 0.029s 13