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.util.*;
public final class k_bonacci
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static int maxn=(int)50;
	static long max_val=(long)(1e9);
	
	public static void main(String args[]) throws Exception
	{
		long s=sc.nextInt();int k=sc.nextInt();
		List<Long> list=new ArrayList<Long>();list.add(0L);list.add(1L);
		for(int i=0;i<maxn;i++)
		{
			long curr=0;
			for(int j=list.size()-1,ptr=k;j>=0 && ptr>0;j--,ptr--)
			{
				curr+=list.get(j);
			}
			if(curr>max_val)
			{
				break;
			}
			list.add(curr);
		}
		long ans=-1;
		for(int i=0;i<list.size();i++)
		{
			if(list.get(i)==s)
			{
				ans=list.get(i);break;
			}
		}
		if(ans!=-1)
		{
			out.println(2+"\n"+ans+" "+0);
		}
		else
		{
			list.remove(1);List<Long> al=new ArrayList<Long>();
			while(s>0)
			{
				int low=0,high=list.size()-1;
				while(low<high)
				{
					int mid=(low+high+1)>>1;long curr=list.get(mid);
					if(curr<=s)
					{
						low=mid;
					}
					else
					{
						high=mid-1;
					}
				}
				al.add(list.get(low));s-=list.get(low);
			}
			out.println(al.size());
			for(long x:al)
			{
				out.print(x+" ");
			}
			out.println("");
		}
		out.close();
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}