← 返回题目列表

Codeforces · 225/B

B. 知名号码

中文机器翻译题面 查看原题

数字 k-bonacci(k 是整数,k > 1)是 Fibonacci 数的推广,确定如下:

- F(k, n) = 0,对于整数n,1 ≤ n < k;
- F(k, k) = 1;
- F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k),对于整数 n,n > k。

请注意,我们仅针对 n 和 k 的整数值确定 k-bonacci 数 F(k, n)。

你有一个数字 s,将其表示为几个(至少两个)不同的 k-bonacci 数字的总和。

输入

第一行包含两个整数 s 和 k (1 ≤ s, k ≤ 109; k > 1)。

输出

在第一行中打印一个整数 m (m ≥ 2),它显示找到的表示中有多少个数字。在第二行中打印 m 个不同的整数 a1, a2, ..., am。每个打印的整数应该是一个 k-bonacci 数。打印的整数之和必须等于 s。

保证答案存在。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

5 2

输出 #1

3
0 2 3

输入 #2

21 5

输出 #2

3
4 1 16