Problem: 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. 

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.

Examples

Input

5 2


Output

3
0 2 3


Input

21 5


Output

3
4 1 16

Solution (in JAVA):

Solution:
import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * Created by jizhe on 2016/1/5.
 */
public class WellknownNumbers {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        StringBuilder out = new StringBuilder();

        int S = in.nextInt();
        int K = in.nextInt();
        int[] bonacci = new int[100000];
        int count = 0;

        bonacci[0] = 1;
        bonacci[1] = 1;
        count = 2;
        int current = 1;
        int k = K+2;
        while( current <= S )
        {
            int prev = bonacci[k-1-K];
            //System.out.printf("prev k: %d, index: %d, prev: %d\n", k-1, k-1-K, prev);
            if( k-1-K < K )
            {
                current = prev+prev;
            }
            else
            {
                current = prev-bonacci[k-1-K-K]+prev;
            }
            //System.out.printf("k: %d, current: %d\n", k, current);
            bonacci[count++] = current;
            k++;
        }

        //System.out.printf("count: %d\n", count);

        int[] numbers = new int[100000];
        int n = 0;
        count--;
        while( S > 0 )
        {
            //System.out.printf("S: %d, bonacci[%d]: %d\n", S, count, bonacci[count]);
            if( S >= bonacci[count] )
            {
                numbers[n++] = bonacci[count];
                S -= bonacci[count];
            }
            count--;
        }

        if( n == 1 )
        {
            numbers[n++] = 0;
        }

        System.out.printf("%d\n", n);
        for( int i = 0; i < n; i++ )
        {
            System.out.printf("%d ", numbers[i]);
        }
        System.out.printf("\n");
    }
}