Fibonacci Sum Decomposition

Given an integer \(N\) satisfying \(1 \leq N \leq 10^{18}\), decompose \(N\) as a sum of distinct Fibonacci numbers. The Fibonacci numbers are generated starting with \(1\) and \(2\) and each subsequent number is the sum of the previous two. That is, the sequence is defined as \(F_1 = 1\), \(F_2 = 2\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \geq 3\).

Your task is to choose a subset of these Fibonacci numbers such that their sum is exactly \(N\). It can be shown that a greedy strategy (selecting the largest Fibonacci number that does not exceed the remaining value of \(N\)) always leads to a valid decomposition. Output the chosen Fibonacci numbers in non-decreasing order separated by spaces.

Note: The answer does not need to be the one provided in the examples as long as the sum matches \(N\) and the numbers are distinct.

inputFormat

The input is given via standard input and consists of a single integer \(N\) \( (1 \leq N \leq 10^{18})\), representing the number to be decomposed.

outputFormat

Output via standard output the distinct Fibonacci numbers (in non-decreasing order) that sum up to \(N\), separated by a single space.

10

2 8