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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;
import java.util.Queue;
public class A {
	
		public static void main(String[] args) throws IOException  {
			FastReader sc=new FastReader();
			int s=sc.nextInt();
			int k=sc.nextInt();
			ArrayList <Integer>l1=new ArrayList<>();
			generateSeries(l1,(int)Math.min(k, 101),s);
			ListIterator<Integer> i=l1.listIterator(l1.size());
			Queue<Integer>q=new LinkedList<>();
	//	for(int j=0;j<l1.size();j++) System.out.print(l1.get(j)+" ");
			long sum=s;
			ArrayList<Integer> l2=new ArrayList<>();
			while(s!=0){
				while(i.hasPrevious() && s>=0){
					int t=i.previous();
					if(s>=t && t>0){
						s-=t;
						l2.add(t);
					}
				}
			}
			if(l2.size()<2) l2.add(0);
			Iterator l=l2.iterator();
			System.out.println(l2.size());
			while(l.hasNext()) System.out.print(l.next()+" ");
			
			
			
			
		}
	   public static void generateSeries(ArrayList<Integer>l1,int k,int s){
		    int i=0;
		    int sum=0;
		    while(sum<=s){
		    l1.add(f(k,i,l1));
		    sum=l1.get(l1.size()-1);
		    i++;
		    }
	   }
	   public static int f(int k,int n,ArrayList <Integer>l1){
		   if(n<k) return 0;
		   if(n==k) return 1;
		   if(n>k) {
			   int d=0;
			   for(int i=1;i<=k;i++){
				   d+=l1.get(n-i);
			   }
			   return d;
		   }
		return 0;
	   }
       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;
		        }
		    }
}