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

public class TC
{
    static int[] memo;
    
    
    static int n,k;
    
    static void fill( int n )
    {
        ArrayList<Integer> temp = new ArrayList();
        /* if( n > k )
            memo = new int[ 2*n+1 ];
        
        else
            memo = new int[ 2*k + 1 ];
        
        Arrays.fill( memo, Integer.MAX_VALUE ); */
        
        /* for( int i=0; i<k; i++ )
        {
            // memo[ i ] = 0;
            temp.add(  0 );
            
            
        } */
        
        // memo[ k ] = 1;
        temp.add( 1 );
        int cnt = 1;
        
        int start = 0;
        int sum = 1;
        
        for( int i=1; i<k; i++ )
        {
            // memo[ k+i ] = sum;
            temp.add( sum );
            sum+= temp.get( cnt );
            
            // if( sum >= Math.max( 2*n+1, 2*k+1  ) )
               // break;
            cnt++;
            
            if( sum > n )
                break;
            
        }
        
        
        
        for( ; true; cnt++ )
        {
            // if( sum >= Math.max( 2*n+1, 2*k+1  ) )
               // break;
            
            if( sum > n )
                break;
            
            temp.add( sum );
            // memo[ cnt ] = sum;
            sum -= temp.get(  start );
            start++;
            sum+= temp.get( cnt );
            
            
        }
        
        memo = new int[ temp.size() ];
        
        for( int i=0; i<temp.size(); i++ )
            memo[ i ] = temp.get( i );
    }
    
    static void solve()
    {
        if( n == 1 )
        {
            System.out.println("2");
            System.out.println("0 1");
            return;
        }
        
        if( n == 2 )
        {
            System.out.println("2");
            System.out.println("0 2");
            return;
        }
        ArrayList<Integer> ret = new ArrayList();
        int res = n;
        int low = 0;
        int high = memo.length;
        
        
        
        boolean flag = true;
        
        while( true )
        {
            int ind;
            
            
            
            //else
            //{
                ind = Arrays.binarySearch( memo, low, high, res);
            //}
            
            
            if( ind >= 0 )
            {
                ret.add( memo[ ind ]);
                res = res-memo[ ind ];
                
                high = ind;
                
                if( res == 0 )
                    break;
                
                continue;
            }
            
            else
            {
                int x = -( ind+1 );
                
                // choose x-1 
                
                ret.add( memo[ x-1 ]);
                res = res - memo[ x-1 ];
                
                high = x-1;
                
                if( res == 0 )
                    break;
                
                
            }
            
            
            
     
        }
        
        System.out.println( ret.size()+1 );
        
        for( int i=0; i<ret.size(); i++ )
        {
            System.out.print( ret.get( i ) + " ");
        }
        
        System.out.println(0 );
        
        
    }
    
    public static void main( String[] args ) throws IOException
    {
        BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
        
     
        String st;
        String[] spl;
        
     
            st = br.readLine();
            spl = st.split( " ");
            
            n = Integer.parseInt( spl[ 0 ]);
            k = Integer.parseInt( spl[ 1 ]);
            
            fill( n );
            solve();
            
}
}