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.*;
import java.io.*;
 
public class File {
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner() {
			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());
		}
	}
		
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		long s=sc.nextLong();
		int k=sc.nextInt();
		List<Long> list=new ArrayList<>();
		int i=0;
		long curr=1;
		list.add(curr);
		
		while(curr<=s)
		{
		    list.add(curr);
		    i=list.size()-1;
		    if(i-k>=0)
		    {
		        curr-=list.get(i-k);
		    }
		    curr+=list.get(i);
		}
		
		long c=0;
		i=list.size()-1;
		StringBuilder sb=new StringBuilder();
		while(s!=0)
		{
		    long x=list.get(i);
		    if(x<=s)
		    {
		        s-=x;
		        c++;
		        sb.append(x+" ");
		    }
		    i--;
		}
		if(c>1)
		{
		    out.println(c);
		    out.println(sb.toString());
		}
		else
		{
		    sb.append(0);
		    out.println(c+1);
		    out.println(sb.toString());
		}
		out.close();
	}
	
	
}