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.*;
import java.security.SecureRandom;
import java.util.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
    
    
    int n = 0;
    ArrayList<Long> f =  new ArrayList<>();
    boolean used[] = new boolean[100000000];
    long ans[] = new long[1000];
    int sz = 0;
    long s;
    boolean win = false;
    
    void dfs(int x) {
        if (s == 0) {
            win = true;
            return;
        }
        for (int i = n - 1;i >= 0; -- i) {
            if (!used[i]) {
                if (s - f.get(i) >= 0) {
                    used[i] = true;
                    s -= f.get(i);
                    ans[sz] = f.get(i);
                    ++ sz;
                    dfs(i);
                    if (win)
                        break;
                    -- sz;
                    used[i] = false;
                    s += f.get(i);              
                }
            }
        }
        
    }
    
    public void solve() throws Exception {

        s = sc.nextLong();
        int k = sc.nextInt();
        
        
        f.add(1l);      
        int last = 0;
        for (int i = k + 1;; ++ i) {
            long x = 0;
            for (int j = 1; j <= k; ++ j) {
                if (i - j < k)
                    break;
                x += f.get(last + 1 - j);
            }
            if (x == s) {
                out.println(2);
                out.print(0 + " " + x);
                return;
            }
            f.add(x);
            ++ last;
            if (f.get(last) >= s) {
                n = last;
                break;
            }
        }
        
        for (int i = n - 1;i >= 0; -- i) {
            used[i] = true;
            s -= f.get(i);
            ans[sz] = f.get(i);
            ++ sz;
            dfs(i);
            if (win)
                break;
            -- sz;
            used[i] = false;
            s += f.get(i);
        }
        
        out.println(sz);
        for (int i = 0;i < sz; ++ i) {
            out.print(ans[i] + " ");
        }
        
    }
    
    
    
    
    /*--------------------------------------------------------------*/
    
    static String filename = "";
    static boolean fromFile = false;
    
    BufferedReader in;
    PrintWriter out;
    FastScanner sc;
    
    public static void main(String[] args) {
        new Thread(null, new Solution(), "", 1 << 25).start();
    }
   
    public void run() {
        try {
            init();
            solve();
        } catch (Exception e) {
            throw new RuntimeException(e);
        } finally {
            out.close();
        }
    }
    
    void init() throws Exception {
        if (fromFile) {
            in = new BufferedReader(new FileReader(filename+".in"));
            out = new PrintWriter(new FileWriter(filename+".out"));
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
        sc = new FastScanner(in);
    }
}

class FastScanner {
    
    BufferedReader reader;
    StringTokenizer strTok;
    
    public FastScanner(BufferedReader reader) {
        this.reader = reader;
    }
    
    public String nextToken() throws IOException {
        while (strTok == null || !strTok.hasMoreTokens()) {
            strTok = new StringTokenizer(reader.readLine());
        }
        
        return strTok.nextToken();
    }
    
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(nextToken());
    }
    
    public BigDecimal nextBigDecimal() throws IOException {
        return new BigDecimal(nextToken());
    }
}