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

Solution:
#include <bits/stdc++.h>
using namespace std;
long long fib_[100];
long long flen = 0;
long long k = 0;
stack<long long> r;
void initfib(const long long k) {
  long long i = 0;
  long long z = 1;
  while (i < k && z < 2000000000) {
    fib_[i] = z;
    z *= 2;
    i++;
  }
  flen = k;
}
long long fib(long long pos) {
  if (pos < k - 1) return 0;
  if (pos == k - 1) return 1;
  pos = pos - k;
  if (pos < flen) return fib_[pos];
  while (flen != pos + 1) {
    fib_[flen] = 0;
    long long i = 0;
    while (i < k && flen - i + 1 >= 0) {
      fib_[flen] += fib_[flen - i - 1];
      i++;
    }
    if (i < k) fib_[flen]++;
    flen++;
  }
  return fib_[pos];
}
long long result[500];
long long reslen;
set<long long> m;
bool solve(long long s, long long maxind) {
  if (s == 0) return true;
  if (m.find(s) != m.end()) return false;
  while (fib(maxind) > s) maxind--;
  while (maxind > 0 && !solve(s - fib(maxind), maxind)) maxind--;
  if (!maxind) {
    m.insert(s);
    return false;
  }
  result[reslen] = fib(maxind);
  reslen++;
  return true;
}
int main(int argc, char* argv[]) {
  m.clear();
  long long s;
  cin >> s >> k;
  initfib(k);
  long long maxind = k - 1;
  while (fib(maxind) <= s) maxind++;
  solve(s, maxind);
  if (reslen == 1) {
    cout << "2\n";
    cout << "0 " << result[0] << endl;
    return 0;
  }
  cout << reslen << endl;
  for (long long i = 0; i < reslen - 1; i++) {
    cout << result[i] << " ";
  }
  cout << result[reslen - 1] << endl;
  return 0;
}