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 javax.print.DocFlavor;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.Buffer;
import java.sql.BatchUpdateException;
import java.util.*;
import java.util.stream.Stream;
import java.util.Vector;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import static java.lang.Math.*;
import java.util.*;
import java.nio.file.StandardOpenOption;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.PriorityQueue;

public class icpc
{
    public static void main(String[] args)throws IOException
    {
        Reader in = new Reader();

        long s = in.nextLong();
        long k = in.nextLong();

        ArrayList<Long> A = new ArrayList<>();
        if(k < 32)
        {
            for(int i=0;i<k-1;i++)
                A.add(0L);
            A.add(1L);
            long sum = 1;
            int count = (int)k;
            while(sum <= s)
            {
                A.add(sum);
                sum += (sum - A.get((count++) - (int)k));
            }
            HashSet<Long> h = new HashSet<>();
            StringBuilder stringBuilder = new StringBuilder();
            for(int i=A.size()-1;i>=0;i--)
            {
                if(A.get(i) <= s && !h.contains(A.get(i)))
                {
                    s -= A.get(i);
                    h.add(A.get(i));
                    stringBuilder.append(A.get(i) + " ");
                }
                if(s == 0)
                    break;
            }
            if(h.size() == 1)
            {
                stringBuilder.append("0");
                System.out.println(h.size() + 1);
            }
            else
            {
                System.out.println(h.size());
            }
            System.out.println(stringBuilder);
        }
        else
        {
            StringBuilder stringBuilder = new StringBuilder();
            long x = 0L;
            int count = 0;
            while(s > 0)
            {
                count++;
                x = (long)Math.pow(2,(long)Math.floor(Math.log(s) / Math.log(2)));
                stringBuilder.append(x + " ");
                s -= x;
            }
            if(count == 1)
            {
                System.out.println(2);
                stringBuilder.append("0");
            }
            else
                System.out.println(count);
            System.out.println(stringBuilder);
        }

    }
}
class Game
{
    int x;
    int y;
    Game(int a,int b)
    {
        this.x = a;
        this.y = b;
    }
}
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(long arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        long L[] = new long [n1];
        long R[] = new long [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(long arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
}
class Node
{
    String a;
    String b;
    Node(String s1,String s2)
    {
        this.a = s1;
        this.b = s2;
    }
    @Override
    public boolean equals(Object ob)
    {
        if(ob == null)
            return false;
        if(!(ob instanceof Node))
            return false;
        if(ob == this)
            return true;
        Node obj = (Node)ob;
        if(this.a.equals(obj.a) && this.b.equals(obj.b))
            return true;
        return false;
    }

    @Override
    public int hashCode()
    {
        return (int)this.a.length();
    }
}
class Reader
{
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1)
        {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
        {
            ret = ret * 10 + c - '0';
        }  while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.')
        {
            while ((c = read()) >= '0' && c <= '9')
            {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}
class SegmentTree
{
    public int nextPowerOfTwo(int num)
    {
        if(num == 0)
            return 1;
        if(num > 0 && (num & (num - 1)) == 0)
            return num;
        while((num &(num - 1)) > 0)
        {
            num = num & (num - 1);
        }
        return num << 1;
    }

}
class FenwickTree
{
    public void update(long[] fenwickTree,long delta,int index)
    {
        index += 1;
        while(index < fenwickTree.length)
        {
            fenwickTree[index] += delta;
            index = index + (index & (-index));
        }
    }
    public long prefixSum(long[] fenwickTree,int index)
    {
        long sum = 0L;
        index += 1;
        while(index > 0)
        {
            sum += fenwickTree[index];
            index -= (index & (-index));
        }
        return sum;
    }
}
class SegmentTree1
{
    public int nextPowerOfTwo(int num)
    {
        if(num == 0)
            return 1;
        if(num > 0 && (num & (num - 1)) == 0)
            return num;
        while((num &(num - 1)) > 0)
        {
            num = num & (num - 1);
        }
        return num << 1;
    }
    public int[] createSegmentTree(int[] input)
    {
        int np2 = nextPowerOfTwo(input.length);
        int[] segmentTree = new int[np2 * 2 - 1];

        for(int i=0;i<segmentTree.length;i++)
            segmentTree[i] = Integer.MAX_VALUE;

        constructSegmentTree(segmentTree,input,0,input.length-1,0);
        return segmentTree;

    }
    private void constructSegmentTree(int[] segmentTree,int[] input,int low,int high,int pos)
    {
        if(low == high)
        {
            segmentTree[pos] = input[low];
            return;
        }
        int mid = (low + high)/ 2;
        constructSegmentTree(segmentTree,input,low,mid,2*pos + 1);
        constructSegmentTree(segmentTree,input,mid+1,high,2*pos + 2);
        segmentTree[pos] = Math.min(segmentTree[2*pos + 1],segmentTree[2*pos + 2]);
    }
    public int rangeMinimumQuery(int[] segmentTree,int qlow,int qhigh,int len)
    {
        return rangeMinimumQuery(segmentTree,0,len - 1,qlow,qhigh,0);
    }
    private int rangeMinimumQuery(int[] segmentTree,int low,int high,int qlow,int qhigh,int pos)
    {
        if(qlow <= low && qhigh >= high)
        {
            return segmentTree[pos];
        }
        else if(qlow > high || qhigh < low)
        {
            return Integer.MAX_VALUE;
        }
        int mid = (low + high)/2;
        return Math.min(rangeMinimumQuery(segmentTree,low,mid,qlow,qhigh,2*pos+1),rangeMinimumQuery(segmentTree,mid+1,high,qlow,qhigh,2*pos+2));
    }
    public void updateSegmentTreeRangeLazy(int[] input,int[] segmentTree,int[] lazy,int startRange,int endRange,int delta)
    {
        updateSegmentTreeRangeLazy(input,segmentTree,lazy,startRange,endRange,delta,0,input.length-1,0);
    }
    private void updateSegmentTreeRangeLazy(int[] input,int[] segmentTree,int[] lazy,int startRange,int endRange,int delta,int low,int high,int pos)
    {
        if(low > high)
        {
            return;
        }
        if(lazy[pos] != 0)
        {
            segmentTree[pos] += lazy[pos];
            if(low != high)
            {
                lazy[2*pos+1] += lazy[pos];
                lazy[2*pos + 2] += lazy[pos];
            }
            lazy[pos] = 0;
        }
        if(startRange > high || endRange < low)
            return;
        if(startRange <= low && endRange >= high)
        {
            segmentTree[pos] += delta;
            if(low != high)
            {
                lazy[2*pos + 1] += delta;
                lazy[2*pos + 2] += delta;
            }
            return;
        }
        int mid = (low + high)/2;
        updateSegmentTreeRangeLazy(input,segmentTree,lazy,startRange,endRange,delta,low,mid,2*pos + 1);
        updateSegmentTreeRangeLazy(input,segmentTree,lazy,startRange,endRange,delta,mid + 1,high,2 * pos + 2);
        segmentTree[pos] += Math.min(segmentTree[2*pos + 1],segmentTree[2*pos + 2]);
    }
    public int rangeMinimumQueryLazy(int[] segmentTree,int[] lazy,int qlow,int qhigh,int len)
    {
        return rangeMinimumQueryLazy(segmentTree,lazy,qlow,qhigh,0,len - 1,0);
    }
    private int rangeMinimumQueryLazy(int[] segmentTree,int[] lazy,int qlow,int qhigh,int low,int high,int pos)
    {
        if(low > high)
            return Integer.MAX_VALUE;
        if(lazy[pos] != 0)
        {
            segmentTree[pos] += lazy[pos];
            if(low != high)
            {
                lazy[2*pos + 1] += lazy[pos];
                lazy[2*pos + 2] += lazy[pos];
            }
            lazy[pos] = 0;
        }
        if(qlow > high || qhigh < low)
            return Integer.MAX_VALUE;
        if(qlow <= low && qhigh >= low)
            return segmentTree[pos];
        int mid = (low + high)/2;
        return Math.min(rangeMinimumQueryLazy(segmentTree,lazy,qlow,qhigh,low,mid,2*pos + 1),rangeMinimumQueryLazy(segmentTree,lazy,qlow,qhigh,mid + 1,high,2*pos + 2));
    }
}