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.*;
import java.util.*;
import java.math.BigInteger;
/*
 * This file was created by ayush in attempt to solve the problem problems
 */
public class main {

    ArrayList<Long> dp = new ArrayList<Long>(); 
    int cnt=0;
    public void fillDP(int n,int k){
	dp.add(1l);
    	for (int i = 0; ; i++) {
			long num = 0;
			for (int j = dp.size() - 1; j >= dp.size() - k && j >= 0; j--) {
				num += dp.get(j);
			}
			if (num > n) break;
			dp.add(num);
	}
	
    }
    public void solve(int n,int k, PrintWriter out) {
	if(k<=32){
		fillDP(n,k);
	}else{
		dp.add(1l);
		dp.add(1l);
		int pow = 1;
		for(int i=1;dp.get(i)<=n;i++){
			dp.add( 1l << pow++ );
		}


	}

//	for(int i=0;i<dp.size();i++){
//		out.println(dp.get(i));
//	}

	long rem=n;
	String ans="0 ";
	int count=1;
	for(int i=dp.size()-1;i>=0;i--){
		if(rem>=dp.get(i)){
			count++;
			rem-=dp.get(i);
			ans+=dp.get(i)+" ";
		}
	}
	out.println(count);
	out.println(ans);



    }

    public static void main(String[] args) throws Exception {
	
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
 	int k = in.nextInt();	
        Date t1 = new Date();
        main solver = new main();
        solver.solve(n,k, out);
        out.flush();
        Date t2 = new Date();
        System.err.println(String.format("Your program took %f seconds", (t2.getTime() - t1.getTime()) / 1000.0));
        out.close();
	
		
	
    }
    static class FastScanner {

    private static BufferedReader reader;
    private static StringTokenizer tokenizer;


    public FastScanner(InputStream in) throws Exception {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = new StringTokenizer(reader.readLine().trim());
    }

    public int numTokens() throws Exception {
        if (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine().trim());
            return numTokens();
        }
        return tokenizer.countTokens();
    }

    public boolean hasNext() throws Exception {
        if (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine().trim());
            return hasNext();
        }
        return true;
    }

    public String next() throws Exception {
        if (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine().trim());
            return next();
        }
        return tokenizer.nextToken();
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws Exception {
        return Float.parseFloat(next());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(next());
    }

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

    public int[] nextIntArray() throws Exception {
        String[] line = reader.readLine().trim().split(" ");
        int[] out = new int[line.length];
        for (int i = 0; i < line.length; i++) {
            out[i] = Integer.valueOf(line[i]);
        }
        return out;
    }

    public double[] nextDoubleArray() throws Exception {
        String[] line = reader.readLine().trim().split(" ");
        double[] out = new double[line.length];
        for (int i = 0; i < line.length; i++) {
            out[i] = Double.valueOf(line[i]);
        }
        return out;
    }

    public Integer[] nextIntegerArray() throws Exception {
        String[] line = reader.readLine().trim().split(" ");
        Integer[] out = new Integer[line.length];
        for (int i = 0; i < line.length; i++) {
            out[i] = Integer.valueOf(line[i]);
        }
        return out;
    }

    public BigInteger[] nextBigIngtegerArray() throws Exception {
        String[] line = reader.readLine().trim().split(" ");
        BigInteger[] out = new BigInteger[line.length];
        for (int i = 0; i < line.length; i++) {
            out[i] = new BigInteger(line[i]);
        }
        return out;
    }

    public String nextLine() throws Exception {
        return reader.readLine().trim();
    }

    public BigInteger nextBigInteger() throws Exception {
        return new BigInteger(next());
    }
    }


   


    static class DEBUG {
        public static void DebugInfo(String disp) {
            System.err.println("DEBUG Info: " + disp);
        }

        public static void DebugVariable(String variable, String value) {
            System.err.println("DEBUG Info: " + variable + " => " + value);
        }


        public static void DebugVariable(String variable, int value) {
            System.err.println("DEBUG Info: " + variable + " => " + value);
        }


        public static void DebugVariable(String variable, long value) {
            System.err.println("DEBUG Info: " + variable + " => " + value);
        }

        public static void DebugArray(int[] value) {
            for (int i = 0; i < value.length; i++) {

                System.err.println("DEBUG Info: " + i + " => " + value[i]);
            }
        }

    }

}