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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting

Greedy algorithms


Solutions:
def s():
	[s, k] = list(map(int, input().split()))
	d = [0]
	d.append(1)
	t = 0
	r = []
	while t < s:
		t = sum(d[-min(k, len(d)):])
		d.append(t)
	for i in reversed(d):
		if i <= s:
			s -= i
			r.append(i)
			if i == 0:
				break
	print(len(r))
	print(*r)
s()


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm, accumulate
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

def num():
	return int(input())

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def pmat2(A):
	for ele in A:
		for j in ele:
			print(j, end='')
		print()

def iseven(n):
	return n % 2 == 0

def seive(r):
	prime = [1 for i in range(r + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(r + 1):
		if prime[i]:
			for j in range(2 * i, r + 1, i):
				prime[j] = 0
	return prime
(s, k) = sp()
f = [0, 1]
while True:
	cur = sum(f[-k:])
	if cur > s:
		break
	f.append(cur)
f = list(set(f))
f.sort()
i = len(f) - 1
ans = []
while s and i > 0:
	if f[i] <= s:
		s -= f[i]
		ans.append(f[i])
	i -= 1
print(len(ans) + 1)
print(*ans + [0])
endtime = time.time()


(s, k) = map(int, input().split())
fib = [0, 1]
for i in range(80):
	g = 0
	for x in range(k):
		if len(fib) - x - 1 < 0:
			break
		g += fib[len(fib) - x - 1]
	fib.append(g)
ans = []
for x in reversed(fib):
	if x <= s:
		s -= x
		ans.append(x)
print(len(ans))
print(' '.join((str(x) for x in ans)))


import sys
input = sys.stdin.readline

def sep():
	return map(int, input().split())

def main():
	(s, k) = sep()
	a = [0, 1]
	ans = []
	while a[-1] < s:
		a.append(sum(a[-k:]))
	a.reverse()
	for i in a:
		if i <= s:
			ans.append(i)
			s -= i
	print(len(ans))
	print(*ans)
main()


(s, k) = list(map(int, input().split(' ')))
a = [0, 1, 1]
while a[-1] < s:
	if len(a) < k:
		a.append(sum(a))
	else:
		t = 0
		for i in range(k):
			t += a[-i - 1]
		a.append(t)
if s == a[-1]:
	print(2)
	print(0, a[-1])
else:
	use = []
	for i in range(len(a)):
		if s >= a[-i - 1]:
			s -= a[-i - 1]
			use.append(a[-i - 1])
	print(len(use))
	for i in use:
		print(i, end=' ')


(s, k) = [int(i) for i in input().split()]
a = [-1, 0, 1, 1]
i = 3
while a[i] <= pow(10, 9):
	i += 1
	a.append(0)
	if i <= k:
		for j in range(1, i):
			a[i] += a[j]
	else:
		for j in range(i - k, i):
			a[i] += a[j]
b = []
for j in range(i, 0, -1):
	if a[j] <= s:
		b.append(a[j])
		s -= a[j]
		if s == 0:
			b.append(0)
			break
print(len(b))
for i in b:
	print(i, end=' ')


(s, k) = map(int, input().split())
f = [1]
while f[-1] < s:
	x = 0
	for i in range(max(0, len(f) - k), len(f)):
		x += f[i]
	f.append(x)
result = [0]
pos = len(f) - 1
while s != 0:
	while f[pos] > s:
		pos -= 1
	result.append(f[pos])
	s -= f[pos]
print(len(result))
print(' '.join(map(str, result)))


def genkbon(s, k):
	if k < 50:
		i = 0
		res = [0]
		while res[i] <= s:
			if i < k:
				res.append(0)
			elif i == k:
				res.append(1)
			elif i == k + 1:
				res.append(1)
			else:
				res.append(2 * res[i] - res[i - k])
			i += 1
		del res[-1]
		return res
	if k >= 50:
		res = [0, 1]
		i = 1
		while res[i] <= s:
			res.append(2 * res[i])
			i += 1
		return res

def solve(s, k, tmp):
	tmp2 = tmp
	while tmp2[-1] > s:
		del tmp2[-1]
	if s == 0:
		return [0]
	if s == 1:
		return [0, 1]
	if s == 2:
		return [0, 2]
	ha = tmp2[-1]
	res = solve(s - ha, k, tmp2)
	return [ha] + res
inp1 = input()
inp = inp1.split()
hlp = genkbon(int(inp[0]), int(inp[1]))
sol = solve(int(inp[0]), int(inp[1]), hlp)
print(len(sol))
for i in sol[:-1]:
	print(i, end=' ')
print(sol[-1])


(s, k) = map(int, input().split())
F = [0, 1]
b = set()
while True:
	f = sum(F[-k:])
	if f > s:
		break
	F.append(f)
for i in reversed(F):
	if i <= s:
		b.add(i)
		s -= i
print(len(b))
print(' '.join(map(str, b)))


[s, k] = [int(x) for x in input().split()]
numbers = [1]
numbers.append(1)
last = 1
index = 1
while last <= s:
	l_index = index - k
	if l_index >= 0:
		last = last * 2 - numbers[l_index]
	else:
		last *= 2
	if last <= s:
		numbers.append(last)
	index += 1
numbers.reverse()
numbers.append(0)
output = []
for i in numbers:
	if i <= s:
		s -= i
		output.append(i)
print(len(output))
print(' '.join([str(x) for x in output]))


(s, k) = map(int, input().split())
(p, t, l) = ([0], [0, 1, 1], 2)
while t[l] < s:
	t.append((t[l] << 1) - (0 if l < k else t[l - k]))
	l += 1
t.reverse()
for i in t:
	if i > s:
		continue
	p.append(i)
	s -= i
	if s == 0:
		break
print(len(p))
print(' '.join(map(str, p)))


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(s, n) = In()
		if n <= 32:
			l = [0] * (n + 1)
			l[n] = 1
			for i in range(n + 1, n + 60):
				total = 0
				for j in range(i - n, i):
					total += l[j]
				l.append(total)
			ans = []
			j = len(l) - 1
			while s > 0:
				if l[j] <= s and l[j] != 0:
					ans.append(l[j])
					s -= l[j]
				j -= 1
			if len(ans) == 1:
				ans.append(0)
			print(len(ans))
			print(*ans)
		else:
			ans = []
			j = 30
			while s:
				t = pow(2, j)
				if t <= s:
					ans.append(t)
					s %= t
				j -= 1
			if len(ans) == 1:
				ans.append(0)
			print(len(ans))
			print(*ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binarySearch(arr, l, r, val):
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == val:
			ans = mid
			break
		elif arr[mid] < val:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans

def fib(k, s):
	arr = []
	i = 1
	temp = True
	l = 0
	while temp:
		if k > i:
			arr.append(0)
			l += 1
			if arr[-1] > s:
				arr.pop()
				l -= 1
				break
			i = k
		elif k == i:
			arr.append(1)
			l += 1
			if arr[-1] > s:
				arr.pop()
				l -= 1
				break
			i += 1
		else:
			if l <= k:
				num = sum(arr)
				arr.append(num)
				l += 1
				if arr[-1] > s:
					arr.pop()
					l -= 1
					break
			else:
				num += arr[-1]
				num -= arr[-k - 1]
				arr.append(num)
				l += 1
				if arr[-1] > s:
					arr.pop()
					l -= 1
					break
			i += 1
	return arr
(s, k) = list(map(int, input().split()))
arr = fib(k, s)
l = len(arr) - 1
ans = arr[l]
lis = [ans]
while ans < s:
	temp = s - ans
	ind = binarySearch(arr, 0, l, temp)
	ans += arr[ind]
	lis.append(arr[ind])
answer = []
a = len(lis)
if a == 1:
	lis.append(0)
	a += 1
for i in range(1, a + 1):
	answer.append(lis[-i])
print(a)
print(' '.join((str(x) for x in answer)))


def power(a, b):
	if b == 0:
		return 1
	elif b % 2 == 0:
		a_1 = a * a
		return pow(a_1, b // 2)
	return a * pow(a, b - 1)

def k_fib(s, k):
	result = [0]
	if k >= 40:
		fibs = [power(2, i) for i in range(40)]
	else:
		fibs = [0] * (k - 1) + [1]
		while fibs[len(fibs) - 1] < s:
			fibs.append(sum(fibs[-k:]))
	while s > 0:
		if fibs[len(fibs) - 1] <= s:
			result.append(fibs[len(fibs) - 1])
			s -= fibs[len(fibs) - 1]
		fibs.pop()
	return result
(S, K) = [int(j) for j in input().split()]
print(len(k_fib(S, K)))
print(*k_fib(S, K))


(s, k) = map(int, input().split())
arr = [0, 1]
k1 = 1
visited = []
mini = 0
while arr[-1] < s:
	arr.append(sum(arr[-k:]))
while s > 0:
	for i in arr:
		if i <= s:
			mini = i
		else:
			break
	s -= mini
	visited.append(mini)
if len(visited) == 1:
	visited.append(0)
print(len(visited))
print(*visited)


import sys
input = sys.stdin.readline
(s, k) = map(int, input().split())
ans = []
if k >= 60:
	f = [0, 1]
	x = 1
	for i in range(60):
		f.append(x)
		x += x
	for i in range(60)[::-1]:
		if s >= f[i]:
			ans.append(f[i])
			s -= f[i]
			if s == 0:
				break
else:
	f = [0] * (k - 1) + [1]
	x = 1
	for i in range(60):
		f.append(x)
		y = x - f[i]
		x += y
	ans = []
	for i in range(60)[::-1]:
		if s >= f[i]:
			ans.append(f[i])
			s -= f[i]
			if s == 0:
				break
ans.append(0)
print(len(ans))
print(*ans)


(s, k) = map(int, input().split())
if k >= 32:
	k_bon = [0]
	for i in range(33):
		k_bon.append(2 ** i)
else:
	k_bon = [0] * (k - 1)
	k_bon.append(1)
	i = k + 1
	c = 0
	while len(k_bon) <= 100:
		next = sum(k_bon[c:i])
		k_bon.append(next)
		i += 1
		c += 1
k_bon = set(k_bon)
i = 0
ans = []
k_bon = sorted(list(k_bon))
while s != 0:
	if k_bon[i] >= s:
		if s == k_bon[i]:
			s -= k_bon[i]
			ans.append(k_bon[i])
			i = 0
		else:
			s -= k_bon[i - 1]
			ans.append(k_bon[i - 1])
			i = 0
	else:
		i += 1
if len(ans) == 1:
	ans.append(0)
print(len(ans))
print(*ans)


(s, k) = map(int, input().split())
f = [0]
f.append(1)
while True:
	cur = sum(f[-k:])
	if cur > s:
		break
	f.append(cur)
f = list(set(f))
f.sort()
ans = []
i = len(f) - 1
while s and i > 0:
	if f[i] <= s:
		s -= f[i]
		ans.append(f[i])
	i -= 1
print(len(ans) + 1)
print(*ans + [0])


(s, k) = map(int, input().split())
(a, b) = ([0, 1], [])
while a[-1] < s:
	a.append(sum(a[-k:]))
for i in reversed(a):
	if i <= s:
		b.append(i)
		s -= i
print(len(b))
print(' '.join(map(str, b)))


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
from collections import *
from bisect import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(sm, k) = gil()

def solve(sm):
	if sm == 0:
		return 0
	kib = deque([1])
	smk = 1
	while smk * 2 <= sm:
		kib.append(smk)
		smk *= 2
		if len(kib) > k:
			smk -= kib.popleft()
	return smk
	return (n, smk)
ans = []
while len(ans) < 2 or sm:
	smk = solve(sm)
	ans.append(str(smk))
	sm -= smk
print(len(ans))
print(' '.join(ans))


(s, k) = list(map(int, input().split()))
a = [1]
i = 0
while s > a[-1]:
	if i == 0:
		a.append(1)
	else:
		a.append(2 * a[-1] - int(a[-k - 1] if i >= k else 0))
	i += 1
b = []
s0 = s
while s > 0:
	(l, r) = (-1, i + 1)
	while r - l > 1:
		m = (l + r) // 2
		if a[m] >= s:
			r = m
		else:
			l = m
	r = min(i, r)
	while a[r] > s:
		r -= 1
	s -= a[r]
	b.append(a[r])
if len(b) == 1:
	b.append(0)
print(len(b))
print(*b)


(s, k) = map(int, input().split())
freq = [1]
while freq[-1] < s:
	x = 0
	for i in range(max(0, len(freq) - k), len(freq)):
		x += freq[i]
	freq.append(x)
res = [0]
idx = len(freq) - 1
while s != 0:
	while freq[idx] > s:
		idx -= 1
	res.append(freq[idx])
	s -= freq[idx]
print(len(res))
print(*res)


(x, y) = map(int, input().split())
dp = []
dp.append(0)
dp.append(1)
n = 2
while 1:
	sm = 0
	for k in range(n - 1, n - y - 1, -1):
		if k == 0:
			break
		sm += dp[k]
	if sm > x:
		break
	dp.append(sm)
	n += 1
dp.reverse()
res = []
n = 0
while n < len(dp) and x >= 0:
	if x >= dp[n]:
		res.append(dp[n])
		x -= dp[n]
	n += 1
print(len(res))
print(*res)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
l = []
(s, k) = li()
i = 0
sum = [0 for i in range(10 ** 6)]
a = sum[:]
a[1] = 1
sum[1] = 1
for i in range(2, 10 ** 13):
	if i <= k:
		a[i] = sum[i - 1]
	else:
		a[i] = sum[i - 1] - sum[i - k - 1]
	if a[i] > s:
		n = i
		break
	sum[i] = sum[i - 1] + a[i]
l = sorted(list(set(l)))
ans = [0]
i = n - 1
while s and i:
	if s - a[i] >= 0:
		ans.append(a[i])
		s -= a[i]
	i -= 1
print(len(ans))
print(*ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest, _heapify_max, _heapreplace_max
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outln(var):
	sys.stdout.write(str(var) + '\n')

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def k_bonacci(n):
	if n < k:
		return 0
	if n == k:
		return 1
	if n in dp.keys():
		return dp[n]
	dp[n] = 0
	for i in range(n - k, n):
		dp[n] += k_bonacci(i)
	return dp[n]
(s, k) = sp()
answer = []
if k <= 32:
	dp = dd(int)
	i = 1
	while True:
		dp[i] = k_bonacci(i)
		if dp[i] >= pow(10, 9):
			break
		i += 1
	arr = list(dp.values())
	while s > 0:
		temp = bl(arr, s)
		if arr[temp] > s:
			temp -= 1
		s -= arr[temp]
		answer.append(arr[temp])
else:
	i = 32
	while i >= 0 and s > 0:
		if pow(2, i) <= s:
			s -= pow(2, i)
			answer.append(pow(2, i))
		i -= 1
if len(answer) < 2:
	answer.insert(0, 0)
outln(len(answer))
print(*answer)


import bisect
(s, k) = list(map(int, input().split()))
f = [0] * 45
for i in range(45):
	if i == 0 or i == 1:
		f[i] = 1
	elif i < k:
		f[i] = sum(f[:i])
	else:
		f[i] = sum([f[i - j] for j in range(1, k + 1)])
ans = [0]
while s > 0:
	i = bisect.bisect_right(f, s)
	ans.append(f[i - 1])
	s = s - f[i - 1]
print(len(ans))
for i in range(len(ans)):
	print(ans[i], end=' ')