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.

Example

Input

7

Output

1 1 2 3 5 8 13