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 B {
	public void solve() throws IOException {
		long s = nextInt();
		int k = nextInt();
		long[] num = new long[46];
		num[1] = 1;
		for(int i = 2; i < num.length; i++){
			int index = Math.max(i-k, 0);
			for(int j = index; j < i; j++){
				num[i] += num[j];
			}
		}
		/*for(long x : num){
			writer.print(x + " ");
		}
		writer.println();*/
		List<Long> ret = new ArrayList<Long>();
		for(int i = num.length-1; i >= 1; i--){
			if( s >= num[i] ){
				ret.add(num[i]);
				s -= num[i];
			}
		}
		if( k > 1 ){
			ret.add(0L);
		}
		writer.println(ret.size());
		for(int i = 0; i < ret.size(); i++){
			writer.print(ret.get(i) + " ");
		}
		writer.println();
	}

	public static void main(String[] args) throws IOException {
		new B().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() throws IOException {
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			solve();
			reader.close();
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

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

	public String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

}