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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.Vector;

/**
 * Created by Rakshit on 16/3/17.
 * Java is Love.. :)
 */
public class WellKnown {

    public static void main(String args[])
    {
        InputStream stream=System.in;
        OutputStream out1=System.out;
        InputReader in = new InputReader(stream);
        PrintWriter out=new PrintWriter(out1);
        Task solver=new Task();
        solver.solve(in,out);
        out.flush();
    }

    static class Task
    {
        long a[]=new long [30];
        Vector<Long>res=new Vector<>();
        public void solve(InputReader in , PrintWriter out)
        {
            a[0]=1;
            for(int i=1;i<30;i++)
            {
                a[i]=2*a[i-1];
            }

            long n,k;

            n=in.nextLong();
            k=in.nextLong();

            if(k>=30)
            {
                while(n!=0)
                {
                    int c=Arrays.binarySearch(a,n);
                    if(c>=0)
                    {
                        res.add(n);
                        n=0;
                    }
                    else
                    {
                        c=-(c+1);
                        c--;
                        res.add(a[c]);
                        n-=a[c];
                    }
                }
            }
            else
            {
                Vector<Long>store=new Vector<>();
                for(int i=1;i<k;i++)
                {
                    store.add((long)0);
                }

                store.add((long)1);
                store.add((long)1);

                for(int i=1;i<k;i++)
                {
                    store.add((long) Math.pow(2,i));
                }

                long j=store.elementAt((int) (2*k-2));
                for(int i = (int) (2*k); j<Math.pow(10,12); i++)
                {
                    long result=0;
                    for(int l=i-1;l>=i-k;l--)
                    {
                        result+=store.elementAt(l);
                    }

                    store.add(result);
                    j=result;
                }

                while(n!=0)
                {
                    int c= Collections.binarySearch(store,n);
                    if(c>=0)
                    {
                        res.add(n);
                        n=0;
                    }
                    else
                    {
                        c=-(c+1);
                        c--;
                        res.add(store.elementAt(c));
                        n-=store.elementAt(c);
                    }
                }
            }

            res.add((long)0);
            out.println(res.size());

            for(int i=0;i<res.size();i++) {
                out.print(res.elementAt(i) + " ");
            }

            out.flush();
        }
    }

    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;

        public InputReader(InputStream st) {
            this.stream = st;
        }

        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}