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:
//package sheet_B;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class WellKnownNumbers {
	public static void main(String[]args)throws IOException{
		MyScanner sc=new MyScanner();
		int s=sc.nextInt();
		int k=sc.nextInt();
		ArrayList<Integer> a=new ArrayList<Integer>();
		a.add(0);
		a.add(1);
		while(true){
			long sum=0;
			for(int i=a.size()-1;i>=Math.max(0, a.size()-k);i--)
				sum+=a.get(i);
			if(sum<=s)
				a.add((int)sum);
			else
				break;
		}
		a.remove(1);
		ArrayList<Integer> ans=new ArrayList<Integer>();
		for(int i=a.size()-1;i>=0 && s>=0;i--){
			if(s>=a.get(i)){
				ans.add(a.get(i));
				s-=a.get(i);
			}
		}
		if(s==0 && ans.size()>1){
			System.out.println(ans.size());
			for(int i=0;i<ans.size();i++)
				System.out.print(ans.get(i)+" ");
			System.out.println();
		}else
			System.out.println(-1);
	}
	
	static class MyScanner {
	      BufferedReader br;
	      StringTokenizer st;
	 
	      public MyScanner() {
	         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;
	      }

	   }
}