Well-known Numbers
Description
Numbers k-bonacci (k is integer, k > 1) are a generalization of Fibonacci numbers and are determined as follows:
- F(k, n) = 0, for integer n, 1 ≤ n < k;
- F(k, k) = 1;
- F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k), for integer n, n > k.
Note that we determine the k-bonacci numbers, F(k, n), only for integer values of n and k.
You've got a number s, represent it as a sum of several (at least two) distinct k-bonacci numbers.
The first line contains two integers s and k (1 ≤ s, k ≤ 109; k > 1).
In the first line print an integer m (m ≥ 2) that shows how many numbers are in the found representation. In the second line print m distinct integers a1, a2, ..., am. Each printed integer should be a k-bonacci number. The sum of printed integers must equal s.
It is guaranteed that the answer exists. If there are several possible answers, print any of them.
Input
The first line contains two integers s and k (1 ≤ s, k ≤ 109; k > 1).
Output
In the first line print an integer m (m ≥ 2) that shows how many numbers are in the found representation. In the second line print m distinct integers a1, a2, ..., am. Each printed integer should be a k-bonacci number. The sum of printed integers must equal s.
It is guaranteed that the answer exists. If there are several possible answers, print any of them.
Samples
5 2
3
0 2 3
21 5
3
4 1 16