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:

F₁ = 1, F₂ = 1, F_i = F_i-1 + F_i-2 với i > 2.

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

Dữ liệu vào:

Cho từ file BAI3.INP chứa số N (3 ≤ N ≤ 2×10⁶).

Dữ liệu ra:

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

Ví dụ:

BAI3.INP
129

BAI3.OUT
89 34 5 1

Giải thích: 129 = 89 + 34 + 5 + 1

BAI3.INP
8

BAI3.OUT
8

Giải thích: 8 = 8