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      =   512 * (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 solveA() throws IOException {

            int s = in.readInt();
            int k = in.readInt();
            
            int[]helper = { 0,
                            1,
                            2,
                            4,
                            8,
                            16,
                            32,
                            64,
                            128,
                            256,
                            512,
                            1024,
                            2048,
                            4096,
                            8192,
                            16384,
                            32768,
                            65536,
                            131072,
                            262144,
                            524288,
                            1048576,
                            2097152,
                            4194304,
                            8388608,
                            16777216,
                            33554432,
                            67108864,
                            134217728,
                            268435456,
                            536870912,
                            };
            
            ArrayList<Integer>answer  = new ArrayList<Integer>();
            
            for (int i = helper.length - 1; i >= 0; i--) {
                if (helper[i] <= s - k) {
                    answer.add(helper[i]);
                    s -= helper[i];
                }
            }
            
            Collections.sort(answer);
            
            out.println(answer.size());
            for (int i = 0; i < answer.size(); i++) {
                out.print(answer.get(i) + " ");
            }
            out.println();
            
        }
        
        public void solve() throws IOException {
            int number = in.readInt();
            int toSum = in.readInt();
            int[] numbers = new int[100];
            numbers[0] = 1;
            int count;
            for (count = 1; numbers[count - 1] < number; count++) {
                for (int j = count - 1; j >= 0 && j >= count - toSum; j--)
                    numbers[count] += numbers[j];
            }
            List<Integer> answer = new ArrayList<Integer>();
            for (int i = count - 1; i >= 0; i--) {
                if (number >= numbers[i]) {
                    answer.add(numbers[i]);
                    number -= numbers[i];
                }
            }
            answer.add(0);
            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));}}
    }
}