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.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.StringTokenizer;

public class New2 implements Runnable {
    List<Integer> list = new ArrayList<Integer>();
    int max;
    void solve() throws IOException {
        int s = readInt();
        int k = readInt();
        List<Integer> result = new ArrayList<Integer>();
        init(s, k);
        while(s != 0) {
            int tmp = find(s);
            result.add(tmp);
            s = s - tmp;
        }

        result.add(0);
        out.println(result.size());

        for(int i = 0 ; i < result.size() ; i++) {
            if(i!=0)
                out.print(" ");
            out.print(result.get(i));
        }
        out.println();
    }

    void init(int value, int k) {
        int pre = 1;
        list.add(pre);
        while(pre < value) {
            int len = list.size();
            pre = 0;
            for(int i = 0; i < k && (len - i - 1) >= 0; i ++) {
                pre += list.get(len-i-1);
            }
            list.add(pre);
        }
        max = list.size() - 1;
    }

    int find(int k) {
        int start = 0; int end = max;
        if(list.get(end) <= k )
            start = end;
        else
            while(start < end - 1) {
                int mid = (start + end) - 1;
                long value = list.get(mid);
                if(value > k)
                    end = mid;
                else
                    start = mid;
            }
        max = start - 1;
        return list.get(start);
    }



    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

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

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("/Users/shenchen/input.txt"));
                out = new PrintWriter("/Users/shenchen/output.txt");
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

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

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }


}