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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.StringTokenizer;
    
/**
 * @Author  Roman Dzhadan
 * @Team    VNTU [Noobs v3.0]
 * @E-Mail  dflash36@gmail.com
 * @Skype   ronex36
 */
public class Main {
        
    public static final String     TYPE              =   IOSystem.STANDART;
    public static final long       TIME_LIMIT        =   2;
    public static final long       MEMORY_LIMIT      =   256 * (1L << 20);
    public static final String     INPUT_FILE_NAME   =   "input.txt";
    public static final String     OUTPUT_FILE_NAME  =   "output.txt";
    public static final boolean    ONLINE_JUDGE      =   System.getProperty("ONLINE_JUDGE") != null;
        
    public static void main(String[] args) throws FileNotFoundException {
        Main task = new Main();
        IOSystem IO = (TYPE.equals(IOSystem.STANDART) ? task.new IOSystem() : task.new IOSystem(INPUT_FILE_NAME, OUTPUT_FILE_NAME));
        new Thread(null, task.new Task(IO), "", MEMORY_LIMIT).start();
    }

    
    class Task implements Runnable {
    //------------------------------------------------------  SOLUTION  -----------------------------------------------------------//   
            
        public void solve() throws IOException {

            long s = in.readInt();
            int k = in.readInt();

            long[] num = new long[100];
            num[0] = 1;

            for (int i = 1; i < 100; i++) {
                long sum = 0;
                for (int j = i - 1; j >= Math.max(0, i - k); j--)
                    sum += num[j];
                num[i] = sum;
            }

            ArrayList<Long> answer = new ArrayList<Long>();
            for (int i = num.length - 1; i >= 0; i--) {
                if (num[i] <= s && num[i] > 0) {
                    answer.add(num[i]);
                    s -= num[i];
                }
            }
            if (answer.size() == 1) {
                answer.add(s);
            }
            if (s != 0) {
                answer.add(s);
            }
            out.println(answer.size());
            for (int i = 0; i < answer.size(); i++) {
                out.print(answer.get(i) + " ");
            }
            out.println();

        }

        
        //-----------------------------------------------------------------------------------------------------------------------------//
        public void run() {
            try {
                long startTime = System.currentTimeMillis();
                solve();
                close();
                long endTime = System.currentTimeMillis();
                long totalMemory = Runtime.getRuntime().totalMemory();
                long freeMemory = Runtime.getRuntime().freeMemory();
                System.err.printf("Time = %.3f ms\n", (endTime - startTime) / 1000.0);
                System.err.printf("Memory = %.3f MB\n", (totalMemory - freeMemory) / (double)(1L << 20));
            }
            catch (Throwable e) {e.printStackTrace(System.err);System.exit(-1);}
        }
        public PrintWriter out;
        public IOSystem in;
        public Task(IOSystem io) {out = io.out; this.in = io;}
        public void close() throws IOException {in.in.close(); out.close();}
    }
    
    class IOSystem {
        public static final String FILE = "file";
        public static final String STANDART = "stdin";
        
        BufferedReader in;
        StringTokenizer tok;
        PrintWriter out;
        
        public IOSystem() {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            tok = new StringTokenizer("");
        }
        
        public IOSystem(String inputFileName, String outputFileName) throws FileNotFoundException {
            in = new BufferedReader(new FileReader(inputFileName));
            out = new PrintWriter(outputFileName);
            tok = new StringTokenizer("");
        }
        
        String readString() throws IOException {while (!tok.hasMoreTokens()) {String line = in.readLine();if (line == null) return null;tok = new StringTokenizer(line);}return tok.nextToken();}
        String readLine() throws IOException {return in.readLine();}
        int readInt() throws IOException {return Integer.parseInt(readString());}
        long readLong() throws IOException {return Long.parseLong(readString());}
        double readDouble() throws IOException {return Double.parseDouble(readString());}
        void debug(Object... o) {if (!Main.ONLINE_JUDGE) {System.err.println(Arrays.deepToString(o));}}
    }
}