Fibonacci Representation Challenge

Given a positive integer n, represent it as a sum of distinct Fibonacci numbers in decreasing order. The Fibonacci sequence for this problem begins with 1 and 2. You must choose a set of Fibonacci numbers such that their sum equals n, and each Fibonacci number is used at most once. This representation is unique. For example, if n = 10, one valid representation is 8 + 2.

Your task is to compute this representation and output the Fibonacci numbers in decreasing order, separated by spaces. Use an efficient approach to generate the Fibonacci sequence up to n and then use a greedy method to choose the largest possible Fibonacci number at each step.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁹), which is provided via standard input.

outputFormat

Output the representation of n as a sum of distinct Fibonacci numbers in decreasing order. The numbers should be printed on one line, separated by spaces, via standard output.

10

8 2