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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;

import javax.naming.spi.DirStateFactory.Result;

public class SomeB {
    static long[] arr2;
    static Stack<Long> result;

    public static boolean choose(int i, int rem, long left) {
        if (left == 0 && rem == 0)
            return true;
        else if (left < 0 || i == -1 || (left != 0 && rem == 0))
            return false;
        else {
            result.push(arr2[i]);
            if (choose(i - 1, rem - 1, left - arr2[i]))
                return true;
            result.pop();
            if (choose(i - 1, rem, left))
                return true;
            return false;
        }
    }

    public static int solvable(int k, int s) {
        long S = s;
        int last = -1;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((S & (1L << i)) != 0) {
                last = i;
                count++;
            }
        }
        if (last < k)
            return count;
        return -1;
    }

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        int s = in.nextInt();
        int k = in.nextInt();
        long[] arr = new long[100];

        arr[0] = 1;
        for (int i = 1; i < arr.length; i++)
            for (int j = 1; j <= k && i - j >= 0; j++)
                arr[i] += arr[i - j];
        int last = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > s) {
                last = i;
                break;
            }
        }
//      if (solvable(k, s) != -1) {
//          System.out.println(solvable(k, s));
//          while (s != 0) {
//              System.out.print((s & -s) + " ");
//              s -= s & -s;
//          }
//          return;
//      }
        arr2 = new long[last + 2];
        arr2[0] = 0;
        for (int i = 1; i < arr2.length; i++)
            arr2[i] = arr[i - 1];
        result = new Stack<Long>();
        for (int i = arr2.length - 1; i >= 0; i--) {
            if (s >= arr2[i]) {
                s -= arr2[i];
                result.push(arr2[i]);
            }
        }
        System.out.println(result.size());
        while (!result.isEmpty()) {
            System.out.print(result.pop() + " ");
        }
        System.out.println();
        // int dep = 2;
        // while (true) {
        // if (choose(arr2.length - 1, dep, s)) {
        // System.out.println(dep);
        // while (!result.isEmpty())
        // System.out.print(result.pop() + " ");
        // System.out.println();
        // break;
        // }
        // dep++;
        // }
    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

}