Description

输入整数n，输出斐波那契数列的前n项。

Input

输入一个整数n(1<=n<=12)。

Output

输出斐波那契数列的前n项。每个数后面都有空格。

Sample Input

6

Sample Output

1 1 2 3 5 8

HINT

斐波那契数列的排列规则为：第1个数和第2个数的值都为1，从第3个数开始，每个数据都等于它前面相邻的两个数据之和。全部数据输出后记得换行。

Source

NBU OJ