Dãy số fibonacy được định nghĩa như sau:

f1= f2= 1

fn= fn-1+ fn-2(với n >= 3)

Bạn hãy viết chương trình in ra n số đầu tiên của dãy số fibonacy.

Input

là số nguyên n (1<= n <= 30)

Output

Là n số fibonacy đầu tiên trên cùng một dòng, mỗi số cách nhau một khoảng trắng.

Sample

Input #1

7

Output #1

1 1 2 3 5 8 13

Problem source: NTUCoder