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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 题意：扩展斐波那契数， 满足以下条件 F[0] = 0 ; F[1] = 1 ; F[n] = F[n] = F[n-1] + F[n-2] + ...
 * + F[n-k] 求该数列中，和为 inputSum 的任何一组斐波那契数的个数和值
 * 
 * 分析：构造满足条件的斐波那契数组，
 * 
 * @author TinyDolphin
 */
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int inputSum;
		int inputK;
		int[] F = new int[100050]; // 存储新的斐波那契数
		int[] ans = new int[1005]; // 存储相加和为 inputSum 的一组斐波那契数
		while (in.hasNext()) {
			inputSum = in.nextInt();
			inputK = in.nextInt();
			F[0] = 0;
			F[1] = 1;
			int sum = F[0] + F[1];
			int end = 0; // 记录 F[index] 数组中小于 inputSum 的最大斐波那契数的下标。
			// 构造新的斐波那契数组 F[n] = F[n-1] + F[n-2] + ... + F[n-k]
			for (int index = 2; F[index - 1] < inputSum; index++) {
				F[index] = sum;
				// 累加，需要减去前面多余的斐波那契数
				sum = sum + F[index] - F[index - inputK >= 0 ? index - inputK : 0];
				end = index;
			}
			sum = 0;
			int count = -1;
			// 找出和为 inputSum 的任意一组数
			for (int index = end; index >= 0; index--) {
				if (sum + F[index] <= inputSum) {
					ans[++count] = F[index];
					sum += F[index];
				}
			}
			if (count == 0) {
				out.println(2);
				out.print(1 + " " + 0 + "\r\n");
			}else {
				// 以下控制输出
				out.println(count + 1);
				for (int index = 0; index <= count; index++) {
					out.print(ans[index] + (index == count ? "\r\n" : " "));
				}
			}
		}
		out.flush();
	}
}