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


public class Bonnaci {
	private static HashMap<Long, Long> results = new HashMap<Long, Long>();
	public static long F(long k, long n){
	 if (results.containsKey(n)){
		 return results.get(n);
	 }
	 else if (n >= 1 && n < k){
		 return 0;
	 }
	 else if(n == k){
		 return 1;
	 }
	 else{
		 long total = 0;
		 for (int i = 1; i <= k; i++){
			 if (i > 100){
				 break;
			 }
			 total += F(k, n-i);
		 }
		 results.put(n, total);
		 return total;
	 }
 }
public static void main(String [] args){
	Scanner scan = new Scanner(System.in);
	int s = scan.nextInt();
	int k = scan.nextInt();
	ArrayList<Long> numbers = new ArrayList<Long>();
	for (int i = k-1; true; i++ ){
		long temp = F(k,i);
		//System.out.println(temp);
		if (temp > s){
			break;
		}
		else{
			if (!numbers.contains(temp)){
			numbers.add(temp);
			}
		}
	}
	int count = 0;
	ArrayList<Long> output = new ArrayList<Long>();
		for(int i = numbers.size()-1; i >= 0; i--){
			if (s-numbers.get(i) >= 0){
				output.add((numbers.get(i)));
				s -= numbers.get(i);
				count += 1;
			}
	}
	System.out.println(count);
	for(int i = 0; i < output.size(); i++){
		if(i != 0){
			System.out.print(" ");
		}
		System.out.print(output.get(i));
	}
	System.out.println();
}
}