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.

Dữ liệu nhập:

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

Dữ liệu xuất:

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.

Ví dụ

input

7

output

1 1 2 3 5 8 13

input

5

output

1 1 2 3 5