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.util.*;
import java.io.*;

public class Codeforces {

    
    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        int s = Reader.nextInt(), k = Reader.nextInt();
        int arr[] = new int[1000];
        arr[1] = 1; arr[2] = 1;
        int i ;
        for(i = 3; i < 1000; i++){
            arr[i] = arr[i - 1] * 2;
            
            if(i -1 > k)
               arr[i] -= arr[i - k - 1];
            
            if(arr[i] > s)
                break;
        }
        
       
        StringBuilder ans = new StringBuilder();
        int count = 0;
        
        while(s != 0){
            if(arr[i] <= s){
                ans.append(arr[i]).append(" ");
                s -= arr[i];
                count++;
            }
            i--;
        }
        
        if(count == 1){
            System.out.println(2);
            System.out.println(ans.append(0));
        }
        
        else
            System.out.println(count + "\n" + ans);
    }
    
    public static int fib(int n){
        
        if(n == 0) 
            return 0;
        
        if(n < 2)
            return 1;
        
        return fib(n - 2) + fib(n - 1);
    }
}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /**
     * call this method to initialize reader for InputStream
     */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    /**
     * get next word
     */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static byte nextByte() throws IOException {

        return Byte.parseByte(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}