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~.

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

• Đọc từ file văn bản chứa số ~N~ (~1 \le N \le 10^9~).

Output

• Ghi 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é và cách nhau một dấu cách.

Sample Input 1

29

Sample Output 1

21 8