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

\(F_1=1;F_2=1;F_i=F_{i-1}+F_{i-2}.\)

Dãy các số Fibonacii đầu tiên: 1, 1, 2, 3, 5, 8, 13, …

Yêu cầu: Cho số nguyên dương \(N\). Liệt kê \(N\) số Fibonacii đầu tiên.

Dữ liệu Vào từ file văn bản FIBS.INP có cấu trúc:

• Dòng 1 chứa một số nguyên dương \(N(1≤N≤50).\)

Kết quả ghi vào file văn bản FIBS.OUT có cấu trúc:

• Gồm một dòng ghi dãy \(N\) số Fibonacii đầu tiên, giữa hai số cách nhau 1 dấu cách.

Sample Input

6

Sample Output

1 1 2 3 5 8