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.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    ArrayList<Boolean> done;
    ArrayList<Integer> data;
    int F(int k, int n){
        if(n<k){return 0;}
        if(k==n){return 1;}
        int index = n-k-1;
        if(done.size()<=index){
            done.add(false);
            data.add(0);
        }
        if(done.get(index)){
            return data.get(index);
        }
        int sum=0;
        for(int i=0; i<k; ++i){
            int tmp = sum;
            sum += F(k, n-(i+1));
            if(sum==tmp){
                // 続けても0しかないのでbreak
                break;
            }
        }
        done.set(index, true);
        data.set(index, sum);
        return sum;
    }
    
    void solve(int s, int k){
        done = new ArrayList<Boolean>();
        data = new ArrayList<Integer>();
        
        for(int i=k+1; F(k, i) <= s; ++i);
        
        HashSet<Integer> ans = new HashSet<Integer>();
        int _s = 0;
        for(int i=data.size()-1; 0<=i; --i){
            if(_s + data.get(i) <= s){
                _s += data.get(i);
                ans.add(data.get(i));
            }
        }
        ans.add(0);
        
        System.out.println(ans.size());
        Iterator<Integer> list;
        list = ans.iterator();
        for(int i=0; i<ans.size(); ++i){
            System.out.print(list.next());
            if(i+1 < ans.size()){
                System.out.print(' ');
            }
        }
        System.out.print('\n');
    }
    
    void io(){
        Scanner sc = new Scanner(System.in);
        
        final int s = sc.nextInt();
        final int k = sc.nextInt();
        
        solve(s, k);
        
        sc.close();
    }
    
    public static void main(String[] args) {
        new Main().io();
    }
    
    void debug(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}