Dãy số Fibonacci được định nghĩa là dãy số vô hạn ~f_0, f_1, f_2, ...,~ như sau: $$f(i)=\begin{cases} {0,\ {nếu}\ i=0} \\ {1,\ {nếu}\ i=1} \\ {f_{i-1}+f_{i-2},\ {nếu}\ i \ge 2} \\ \end{cases}$$ Các số đầu tiên trong dãy Fibonacci: ~1,1,2,3,5,8,…~

Yêu cầu

Nhập vào số nguyên ~n~, xuất ra dãy số Fibonacci sao cho phần tử lớn nhất không lớn hơn ~n~.

Dữ liệu

Một dòng duy nhất, gồm số nguyên ~n~ ~(0< n\le 10^3)~.

Kết quả

Ghi ra dãy số Fibonacci theo yêu cầu, mỗi số cách nhau một khoảng cách.

Input

11

Output

1 1 2 3 5 8