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.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Random;
import java.util.StringTokenizer;

    public class Main {
            static BufferedReader reader;
            static StringTokenizer tokenizer;
            static PrintWriter writer;
            static Random random;

            static int generateRandom(int n) {
                return Math.abs(random.nextInt()) % n;
            }
            
            static int nextInt() throws IOException {
                    return Integer.parseInt(nextToken());
            }

            static long nextLong() throws IOException {
                    return Long.parseLong(nextToken());
            }

            static double nextDouble() throws IOException {
                    return Double.parseDouble(nextToken());
            }

            static String nextToken() throws IOException {
                    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                            tokenizer = new StringTokenizer(reader.readLine());
                    }
                    return tokenizer.nextToken();
            }

            public static void main(String[] args) throws IOException {
                    reader = new BufferedReader(new InputStreamReader(System.in));
                    tokenizer = null;
                    writer = new PrintWriter("input.txt");
                    random=new Random();
                    solve();
                    reader.close();
                    writer.close();
            }

            private static void solve() throws IOException {
                int s=nextInt();
                int k=nextInt();
                int[] f=new int[10000];
                int i=1;
                f[0]=0;
                f[1]=1;
                while (f[i]<=s)
                {
                    for (int j=0;j<k;j++)
                        if((i-j)>=0)                            
                            f[i+1]+=f[i-j];
                        else
                            break;
                    i++;
                }
                i--;
                int c=0;
                int[] g=new int[10000];
                while (s!=0)
                {
                    c++;
                    s-=f[i];
                    g[c-1]=f[i];
                    if (s==0)
                        break;
                    while (f[i]>s)
                        i--;
                }
                
                if (c==1)
                    {g[c]=0;c++;}
                System.out.println(c);
                for (int j=0;j<c;j++)
                    System.out.print(g[j]+" ");
            }


    }