Dãy Fibonacci là dãy gồm các số: $1,1,2,3,5,8,...$ được xác định bởi công thức sau:

$F_1=1,F_2=1$

$F_i=F_{i-1}+F_{i-2}$ với $i>2$

Yêu cầu

Hãy biểu diễn một số tự nhiên $N$ thành tổng ít nhất các số Fibonacci khác nhau.

Input

Một dòng duy nhất chứa số $N$ $(1\le N\le {10}^9)$

Output

In ra biểu diễn số $N$ thành tổng ít nhất các số Fibonacci khác nhau. Các số ghi trên cùng một dòng theo thứ tự từ lớn đến bé cách nhau một dấu cách

Sample Test

Input 1

2

Output 1

2

Input 2

29

Output 2

21 8

Ràng buộc

• $50\mathrm{\%}$ số test tương ứng $50\mathrm{\%}$ số điểm với $1\le N\le {10}^4$

• $50\mathrm{\%}$ số test tương ứng $50\mathrm{\%}$ số điểm với ${10}^4<N\le {10}^9$