#P55064. 狱吏问题

狱吏问题

题目描述

某王国对囚犯进行大赦,让一狱吏n次通过一排锁着的n间牢房,每通过一次按所定规则转动门锁,每转动一次,原来锁着的被打开,原来打开的被锁上;通过n次后,门锁开着的,牢房中的犯人放出,否则犯人不得获释.转动门锁的规则是这样的,第一次通过牢房,要转动每一把门锁,即把全部锁打开;第二次通过牢房时,从第二间开始转动,每隔一间转动一次;第k次通过牢房,从第k间开始转动,每隔k-1 间转动一次;问通过n次后,那些牢房的锁仍然是打开的?

输入格式

一行一个整数n

输出格式

用空格隔开每个数字

样例

输入样例1

5

输出样例1

1 4

输入样例2

30

输出样例2

1 4 9 16 25

数据范围与提示

n<=1000