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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;


public class B {
	
	// -- DEBUG switch --
	static final boolean DBG = false;
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	
	
	public static void main(String[] args) throws IOException {

		int s = i(), k = i();
		if (s == 1){
			pw.println(2);
			pw.println(0 + " " + 1);
			pw.close();
			return;
		}

		
		int len = 100;
		int[] e = new int[len]; 
//		boolean[] v = new boolean[1000000001];
		e[0] = 1; 
		int sum = e[0], s2 = s + 50;
		int i = 1;
		for (; i<len; i++){
			e[i] = sum;

			if (i<k)
				sum += e[i];
			else
				sum = sum + e[i] - e[i-k];
			if (sum >= s2)
				break;
		}
		
		if (DBG){
			for (int j = i; j>=0; j--)
				pw.println("f(" + j + ") = " + e[j]);
		}
		int cnt = 0;
		StringBuilder sb = new StringBuilder();
		while (i>=0){
			
			if (e[i] <= s){
				cnt++;
				sb.append(e[i] + " ");
				s -= e[i];
				if (s == 0)
					break;
//				v[e[i]] = true;
			}
			i--;
		}
		if (cnt == 1){
			cnt++;
			sb.append(0);
		}
		pw.println(cnt);
		pw.println(sb.toString());
		pw.close();
	}
	
	static int i() throws IOException{
		st.nextToken();
		return (int)st.nval;
	}
	
	static long l() throws IOException {
		st.nextToken();
		return (long)st.nval;
	}

	static double d() throws IOException {
		st.nextToken();
		return st.nval;
	}
	static String s() throws IOException{
		st.nextToken();
		return st.sval;
	}
}