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 PYTHON):

Solution:
#coding=utf-8

#import Set
def F(k,n):
	if 1 <= n and n < k:
		return 0
	if n == k:
		return 1
	return sum([F(k,i) for i in range(n-k,n)])
	
#for i in range(1,20):
#	for j in range(1,20):
#		print "%3d"%F(i,j),
#	print 

def Gen_F(k,MAX):
	if k == 1:
		return [0,1]
	L = [0,1]
	l = -k + 2
	kb = 1
	while kb <= MAX:
#		print kb,l,l+k
		L.append(kb)
		kb = kb * 2
		if l >= 0:
			kb = kb - L[l]
		l = l + 1
	return L
	
s,k = map(int, raw_input().split())
FL =  Gen_F(k,s)

#print [F(k,i) for i in range(k,k+20)]
#print FL

FL = list(reversed(sorted(list(set(FL)))))

#print FL

ans = []
for i in FL:
	if s >= i:
		#print s,i
		ans.append(i)
		s = s - i
		
print len(ans)
for i in ans:
	print i,
print