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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Solver {

	public static void main(String[] Args) throws NumberFormatException, IOException {
		new Solver().Run();
	}

	PrintWriter pw;
	StringTokenizer Stok;
	BufferedReader br;

	public String nextToken() throws IOException {
		while (Stok == null || !Stok.hasMoreTokens()) {
			Stok = new StringTokenizer(br.readLine());
		}
		return Stok.nextToken();
	}

	public int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	int sum;
	int k;
	long[] seq;
	int kol=0;
	long[] res;
	
	public void Run() throws NumberFormatException, IOException {
		//br = new BufferedReader(new FileReader("input.txt"));
		//pw = new PrintWriter("output.txt");
		br=new BufferedReader(new InputStreamReader(System.in));
		pw=new PrintWriter(new OutputStreamWriter(System.out));
		sum=nextInt();
		k=nextInt();
		
		seq=new long[1000000];
		res=new long[1000000];
		
		
		seq[0]=1;
		seq[1]=1;
		int i=1;
		while (seq[i]<=sum){
			i++;
			seq[i]=2*seq[i-1];
			if (i-k-1>=0)
				seq[i]-=seq[i-k-1];
		}
		
		kol++;
		res[kol-1]=0;
		while (sum>0){
			while (seq[i]>sum){
				i--;
			}
			kol++;
			res[kol-1]=seq[i];
			sum-=seq[i];
		}
		
		pw.println(kol);
		for (i=0; i<kol; i++){
			pw.print(res[i]);
			pw.print(' ');
		}
		pw.flush();
		pw.close();
	}

}