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.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;


public class B {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);
		int s = scr.nextInt();
		int k = scr.nextInt();
		
		
		ArrayList<Integer> digits = new ArrayList<>();
		digits.add(0);
		digits.add(1);
		
		int d = 1;
		
		for (int j = 1; j < k; j++){
			d = d*2;
			digits.add(d);
			if (d > s) break;
		}
		
		if (d < s) {
			d = d*2 - 1;
			digits.add(d);
		}	
		
		int sum = d;
		int n = k + 2; //2*k + 2 - k;
		while (d < s){
			d = d + d - digits.get(n - (k+1));
			digits.add(d);
			n++;
		}		
	
		LinkedList<Integer> Kb = new LinkedList<>();
		int ind = digits.size()-1;
		if (d > s) ind--;
		int num; 
		while ((ind >= 0) && (s > 0)){
			num = digits.get(ind);
			if (s >= num) {
				s = s - num;	
				Kb.add(num);
			}
			ind--;			
		}
					
		if (s != 0) System.out.println("failed");
		
		if (Kb.size() == 1){
			Kb.addFirst(0);
		}

		PrintWriter pw = new PrintWriter(System.out);
		pw.println(Kb.size());
		boolean first = true;
		for (int b: Kb){
			pw.print((first ? "" : " ") + b);
			first = false;
		}
		pw.flush();
		pw.close();
	}

}