Hide

Problem A
Minimal Fibonacci Sums

Languages en sv

All positive integers can be written as a sum of Fibonacci numbers (for example, the trivial solution $1 + 1 + 1 + \dots + 1$). A harder problem is to write it as the sum of as few Fibonacci numbers as possible. For example, $7$ can be written as $2 + 5$, while $12$ requires three numbers: $1 + 3 + 8$. Your task is to write a program that finds this shortest representation.

Input

The input consists of a single integer between $1$ and $10^9$.

Output

Output a shortest sequence of Fibonacci numbers that sum to the input. You should output them in increasing order, separated by spaces. If there are several possible shortest sequences, any one will be accepted.

Sample Input 1 Sample Output 1
7
2 5
Sample Input 2 Sample Output 2
12
1 3 8
Sample Input 3 Sample Output 3
3
3

Please log in to submit a solution to this problem

Log in