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.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Sunits789
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
        long arr[]=new long[100];
        Arrays.fill(arr,Long.MAX_VALUE);
        int n=in.nextInt();
        if(n==1){
            out.println("2");
            out.println("0 1");
            return;
        }
        if(n==2){
            out.println("2");
            out.println("0 2");
            return;
        }
        int k=in.nextInt();
        arr[0]=1;
        int fl=0;
        for(int i=1;i<=50;i++){
            int kcount=0;
            arr[i]=0;
            for(int ind=i-1;ind>=0&&kcount<k;ind--,kcount++){
                arr[i]+=arr[ind];
                //fl++;
            }
            fl++;
            //System.out.println(i+" "+arr[i]);
            if(arr[i]>n){
                i=50;
            }
        }
        fl+=3;
        //System.out.println(fl);
        long ans[]=new long[50];
        int ansl=0;
        boolean f=false;
        while (n!=0){
            for(int i=fl-1;i>=0;i--){
                //System.out.println(i+" "+arr[i]);
                if(arr[i]<=n){
                    ans[ansl]=arr[i];
                    n-=arr[i];
                    ansl++;
                    f=true;
                    i=-1;
                }
            }
        }
        out.println(ansl+1);
        out.print("0 ");
        for(int i=0;i<ansl;i++){
            out.print(ans[i]+" ");
        }
	}
}

class InputReader{
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    public String next(){
        while (tokenizer == null||!tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }
            catch (IOException e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt(){
        return Integer.parseInt(next());
    }

    }