Well-known Numbers

题意翻译

定义$k$-bonacci数列${Fn}:Fi=0(i<k),Fi=1 (i=k),Fi=\sum_{j=i-k}^{n-1}Fj$ 给出$s\ (s≤10^9)$和$k\ (k≤10^9)$，将$s$拆成若干个$k$-bonacci数之和。

题目描述

Numbers $ k $ -bonacci ( $ k $ is integer, $ k&gt;1 $ ) are a generalization of Fibonacci numbers and are determined as follows: - $ F(k,n)=0 $ , for integer $ n $ , $ 1<=n&lt;k $ ; - $ F(k,k)=1 $ ; - $ F(k,n)=F(k,n-1)+F(k,n-2)+...+F(k,n-k) $ , for integer $ n $ , $ n&gt;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.

输入输出格式

输入格式

The first line contains two integers $ s $ and $ k $ $ (1<=s,k<=10^{9}; k&gt;1) $ .

输出格式

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 $ a_{1},a_{2},...,a_{m} $ . 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.

输入输出样例

输入样例 #1

5 2

输出样例 #1

3
0 2 3

输入样例 #2

21 5

输出样例 #2

3
4 1 16