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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.StringTokenizer;



public class Main {
	static class MyReader{
	    private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    MyReader(Reader r) throws IOException{
	        reader = new BufferedReader(r);
	    }
	    public int nextInt() throws IOException {
	        return Integer.parseInt(nextToken());
	    }
	    public long nextLong() throws IOException{
	    	return Long.parseLong(nextToken());
	    }
	    public double nextDouble() throws IOException{
	    	return Double.parseDouble(nextToken());
	    }
	    public String nextToken() throws IOException {
	        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            tokenizer = new StringTokenizer(reader.readLine());
	        }
	        return tokenizer.nextToken();
	    }
	}
	public static void main(String []args) throws IOException{
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
		MyReader reader = new MyReader(new InputStreamReader(System.in));
		int s = reader.nextInt();
		int k = reader.nextInt();
		int []a = new int[10000];
		a[0]=a[1]=1;
		int j =0;
		for (int i = 2; i < 10000;++i){
			int t = i-k-1;
			a[i]=2*a[i-1];
			if (t>=0)
				a[i]-=a[t];
			if (a[i]>=s) {j=i; break; }
		}
		ArrayList<Integer> ans = new ArrayList<>();
		for (int i = j; i>=0; --i){
			if (s==0)
				break;
			if (s>=a[i]){
				ans.add(a[i]);
				s-=a[i];
			}
		}
		writer.println(ans.size()+1);
		for (int i = 0; i < ans.size(); ++i){
			writer.print(ans.get(i)+" ");
		}
		writer.print("0");
		writer.close();
	}
	
}