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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Solver {

    StringTokenizer st;
    BufferedReader in;
    PrintWriter out;

    public static void main(String[] args) throws NumberFormatException, IOException {
        Solver solver = new Solver();
        solver.open();
        long time = System.currentTimeMillis();
        solver.solve();
        if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
            System.out.println("Spent time: " + (System.currentTimeMillis() - time));
        }
        solver.close();
    }

    public void open() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
    }

    public String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextToken());
    }

    
    public void solve() throws NumberFormatException, IOException {
        long s = nextLong();
        int k = nextInt();
        int n = 0;
        long[] fres = new long[100];
        
        fres[n++] = 0;
        fres[n++] = 1;
        
        while(fres[n-1]<s){
            long cur = 0;
            for(int j=n-1,l=k;j>=0 && l>0;j--,l--){
                cur+=fres[j];
            }
            fres[n++] = cur;
        }
        
        
        
        List<Long> result = new ArrayList<Long>();
        
        while(s>0){
            long tmp = fres[--n];
            if (tmp<=s){
                s-=tmp;
                result.add(tmp);
            }
        }
        result.add(0l);
        
        out.println(result.size());
        for(long r : result){
            out.print(r+" ");
        }
    }

    public void close() {
        out.flush();
        out.close();
    }

}