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.*;

import static java.util.stream.Collectors.joining;

/**
 * _225B
 * O(log(n)*log(log(n))) time
 * O(log(n)) space
 *
 * @author artyom
 */
public class _225B implements Runnable {
    private BufferedReader in;
    private PrintStream out;
    private StringTokenizer tok;

    private void solve() throws IOException {
        int n = nextInt(), k = nextInt();
        List<Integer> ls = new ArrayList<>();
        ls.add(0);
        int p = 1;
        for (int i = 1; p <= n; i++) {
            ls.add(p);
            if (i < k) {
                p <<= 1;
            } else {
                break;
            }
        }
        p = (p << 1) - 1;
        if (p <= n) {
            ls.add(p);
            for (int i = 1; ; i++) {
                p = (p << 1) - ls.get(i);
                if (p <= n) {
                    ls.add(p);
                } else {
                    break;
                }
            }
        }
        int[] ary = new int[ls.size()];
        for (int i = 0; i < ary.length; i++) {
            ary[i] = ls.get(i);
        }
        Queue<String> fact = new LinkedList<>();
        do {
            int i = Arrays.binarySearch(ary, n);
            if (i < 0) {
                i = -i - 2;
            }
            fact.add(String.valueOf(ary[i]));
            n -= ary[i];
        } while (n > 0);
        fact.add("0");
        out.println(fact.size());
        out.print(fact.stream().collect(joining(" ")));
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _225B().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = System.out;
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private int[] readIntArray(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        return arr;
    }

    private static int getMax(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int i = 0, n = a.length; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }

    private static int getMin(int[] a) {
        int min = Integer.MAX_VALUE;
        for (int i = 0, n = a.length; i < n; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        return min;
    }
}