|
Лимит времени 500/1000/1000/1000 мс. Лимит памяти 16000/16000/16000/16000 Кб.
Вася подарил своему племяннику Пете конструктор юного электрика и пытался его приучить к науке. Конструктор состоит и кнопок, проводов и лампочек. Вася подсоединил все кнопки последовательно ко всем лампочкам. Но вот незадача, Петя еще маленький и не понимает, зачем все это надо, но вот панель с кнопками ему явно понравилась. Пете очень понравилось нажимать кнопки, особенно то, что если нажать на кнопку один раз, то лампочка светится. Если нажать на эту же кнопку второй раз, то лампочка уже не светится. Петя конечно еще маленький, но сразу придумал игру для этого конструктора. Первый раз он проходил панель, нажимая каждую кнопку по-очереди. Второй раз Петя нажимал только четные кнопки. Третий раз нажимал только каждую третью. Четвертый раз, каждую четвертую кнопку. И т.д. пока в последний проход он не нажимал только последнюю кнопку. Петя делал столько проходов по кнопкам, сколько было кнопок. Васе стало интересно, если в начале все лампочки потушены, то какие лампочки в конце останутся светиться? Вася решил это за «полиномиальное» время для любого количества кнопочек. Формат входных данных В единственной строке содержится целое положительное число N, количество кнопочек на панели. (N ≤ 2*109) Формат выходных данных Вывести все номера горящих лампочек в возрастающем порядке. Каждый номер выводить в отдельной строке.
|