printРабочее место участника

printЗадачи

1455. Beat the jocks

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Constraints
`1\ ≤\ N\ ≤\ 10^9`

Sample Input 1

1

Sample Output 1

1

Sample Input 2

5

Sample Output 2

1 4
Source: NEERC ICPC, Far Eastern subregion, 2009
loading