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.lang.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Practice{
	
	
	 static class FastReader {
	        BufferedReader br;
	        StringTokenizer st;
	 
	        public FastReader()
	        {
	            br = new BufferedReader(
	                new InputStreamReader(System.in));
	        }
	 
	        String next()
	        {
	            while (st == null || !st.hasMoreElements()) {
	                try {
	                    st = new StringTokenizer(br.readLine());
	                }
	                catch (IOException e) {
	                    e.printStackTrace();
	                }
	            }
	            return st.nextToken();
	        }
	 
	        int nextInt() { return Integer.parseInt(next()); }
	 
	        long nextLong() { return Long.parseLong(next()); }
	 
	        double nextDouble()
	        {
	            return Double.parseDouble(next());
	        }
	 
	        String nextLine()
	        {
	            String str = "";
	            try {
	                str = br.readLine();
	            }
	            catch (IOException e) {
	                e.printStackTrace();
	            }
	            return str;
	        }
	    }
	 
	 static class Pair{
		 	
		}
			
	 static int  gcd(int a, int b) {
	    if (b == 0) {
	        return a;}
	    else {
	        return gcd(b, a % b);}}
	   
	 public static void main(String[] args)
	    {
	        FastReader sc = new FastReader();
	        
	          
	        	 int s=sc.nextInt();
	        	 int k=sc.nextInt();
	        	 LinkedList<Integer>ll=new LinkedList<>();
	        	 
	        	 ll.add(1);
	        	 int ind=0;
	        	 int forward=1;
	        	 int trailing=0;
	        	 while(ll.get(ind)<s) {
	        		 int add=forward-trailing;
	        		 ll.add(add);
	        		 ind++;
	        		 forward+=ll.get(ind);
	        		 if(ind>=k) {
	        			 trailing+=ll.get(ind-k);
	        		 }
	        	 }
	        	 
	             LinkedList<Integer> ansll=new LinkedList<>();
	             int sum=0;
	             for(int i=ll.size()-1;i>=0;i--)
	                {
	                    int ele=ll.get(i);
	                    if(sum+ele<=s)
	                      {
	                          sum+=ele;
	                          ansll.add(ele);
	                      }
	                }
	             if(ansll.size()==1) {
	               ansll.add(0);}
        		 System.out.println(ansll.size());

	             for(int j:ansll) {
	            	 System.out.print(j+" ");
	             }

	    }
	 }