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.*;
import java.util.*;

public class tB {
    public static void main(String[] args) throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        Scanner in;
        PrintWriter out;
        if (oj) {
            in = new Scanner(System.in);
            out = new PrintWriter(System.out);
        }
        else {
            Reader reader = new FileReader("input.txt");
            Writer writer = new FileWriter("output.txt");
            in = new Scanner(new BufferedReader(reader));
            out = new PrintWriter(writer);
        }
        long n, k;
        n = in.nextLong();
        k = in.nextLong();
        long[] a = new long[1000];
        a[0] = 1;
        a[1] = 1;
        int num = 0;
        for (int i = 2; i < 1000; i++) {
            long cur = 0;
            for (int j = 0; j < k && i - j - 1 >= 0; j++)
                cur = cur + a[i - j - 1];
            if (cur > n) {
                num = i;
                break;
            }
            a[i] = cur;
        }
        long curn = n;
        ArrayList<Long> ans = new ArrayList<Long>();
        for (int j = num - 1; j >= 1 && curn > 0; j--)
            if (a[j] <= curn) {
                curn = curn - a[j];
                ans.add(a[j]);
            }
        if (ans.size() == 1)
            ans.add(new Long(0));
        out.println(ans.size());
        for (int i = 0; i < ans.size(); i++) {
            out.print(ans.get(i) + " ");
        }
        out.println();
        out.flush();
    }

}