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.InputStream;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;



public class B {
	static long[] FIB;
	static long S,K;
	public static void main(String[] args) throws Exception{
		FastScanner sc =new FastScanner(System.in);
		S = sc.nextLong();
		long SS = S;
		K = sc.nextLong();
		FIB = new long[1000000];
		int place = 0;
		while(F(place)<Integer.MAX_VALUE)place++;
		HashSet<Long> HS = new HashSet<Long>();
		for(int a=place;a>=0;a--){
		//	System.out.print(FIB[a]+" ");
			if(FIB[a]<0)continue;
			if(FIB[a]==S){
				HS.add(FIB[a]);
				HS.add(0L);
				break;
			}
			if(FIB[a]<=SS&&FIB[a]!=S&&!HS.contains(FIB[a])){
				SS-=FIB[a];
				HS.add(FIB[a]);
				if(SS==0)break;
			}
		}
		System.out.println(HS.size());
		for(Long x : HS)System.out.print(x+" ");

	}

	private static long F(int N) {
		if(FIB[N]!=0)return FIB[N];
		if(N<=1)return FIB[N]=0;
		if(N==2)return FIB[N]=1;
		for(int a=1;a<=K;a++){
			if(N-a<0)break;
			FIB[N]+=F(N-a);
		}
		return FIB[N];
		
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) throws Exception{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer(br.readLine().trim());
		}
		public int numTokens() throws Exception {
			if(!st.hasMoreTokens()){
				st = new StringTokenizer(br.readLine().trim());
				return numTokens();
			}
			return st.countTokens();
		}
		public String next() throws Exception {
			if(!st.hasMoreTokens()){
				st = new StringTokenizer(br.readLine().trim());
				return next();
			}
			return st.nextToken();
		}
		public double nextDouble() throws Exception{
			return Double.parseDouble(next());
		}
		public float nextFloat() throws Exception{
			return Float.parseFloat(next());
		}
		public long nextLong() throws Exception{
			return Long.parseLong(next());
		}
		public int nextInt() throws Exception{
			return Integer.parseInt(next());
		}
		public String nextLine() throws Exception{
			return br.readLine().trim();
		}
	}


}