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.*;
import static java.lang.Math.*;
import java.math.*;
public class ProblemB {
	void run() {
		Scanner sc = new Scanner(System.in);
		int sum = sc.nextInt();
		int k = sc.nextInt();
		ArrayList<BigInteger> out = getSum(sum, k);
		p("%d\n", out.size());
		for (BigInteger z : out) {
			p("%s ", z);
		}
		p("\n");
	}

	ArrayList<BigInteger> getSum(int sum, int k){
		ArrayList<BigInteger> out = new ArrayList<BigInteger>();
		k = Math.min(k, 1000);
		BigInteger base[] = new BigInteger[k];
		
		BigInteger kk = BigInteger.valueOf(sum);

		while (kk.compareTo(BigInteger.ZERO) == 1) {
			Arrays.fill(base, BigInteger.ZERO);
			BigInteger s = BigInteger.ONE;
			base[k-1] = BigInteger.ONE;

			while (s.compareTo(kk) == -1) { // 0 < ourNumber
				s = doSum(base);
				// shift stuff
				BigInteger newBase[] = new BigInteger[k];
				newBase[k-1] = s;
				for (int i=k-2; i>=0; i--) {
					newBase[i] = base[i+1];
				}
				base = newBase;
				d("base = ", base);
			}
			BigInteger testNo;
			if (base[k-1].compareTo(kk) == 1) {
				testNo = base[k-2];
			} else {
				testNo = base[k-1];
			}

			kk = kk.subtract(testNo);
			d("Left: ", kk);
			out.add(testNo);
		}
		
		if (out.size() == 1) {
			out.add(BigInteger.ZERO);
		}
		return out;
	}

	BigInteger doSum(BigInteger[] base) {
		BigInteger sum = BigInteger.ZERO;
		for (int i=0; i<base.length; i++) {
			sum = sum.add(base[i]);
		}
		return sum;
	}


	boolean contains(int a, int b, int[] check) {
		return (Arrays.binarySearch(check, a) >= 0 && Arrays.binarySearch(check, b) >= 0);
	}

	boolean debug = false;
	void p(String f, Object...params) {
		System.out.printf(f, params);
	}
	void d(Object...params) {
		if (debug) {
			p("DEBUG: %s\n", Arrays.deepToString(params));
		}
	}
	public ProblemB(String[] args) {
		if (args.length > 0 && args[0].equals("debug")) {
			debug = true;
		}
	}
	public static void main(String[] args) {
		new ProblemB(args).run();
	}
}