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.*;
public class ProblemB {
	int M = 100;
    void run() {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int K = sc.nextInt();
		int[] vals = new int[M];
		vals[1] = 1;
		for (int i = 2; i < M; ++i) {
			for (int j = i-1; j >= max(0, i-K); --j) {
				vals[i] += vals[j];
			}
			if (vals[i] > S) {
				break;
			}
		}
		List<Integer> res = new ArrayList<Integer>();
		int i = M-1;
		while (vals[i] == 0) {
			--i;
		}
		while (S > 0) {
			while (vals[i] > S) {
				--i;
			}
			res.add(vals[i]);
			S -= vals[i];
		}
		res.add(0);
		p("%s\n", res.size());
		for (int r : res) {
			p("%d ", r);
		}
		p("\n");
    }

    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));
        }
    }
    void die() {
        throw new RuntimeException();
    }
    public ProblemB(String[] args) {
        if (args.length > 0 && args[0].equals("debug")) {
            debug = true;
        }
    }
    public static void main(String[] args) {
        new ProblemB(args).run();
    }
}