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>
#pragma GCC optimize("O3")
const long long mod1 = 998244353;
const long long mod2 = 1000000007;
long long pow(long long a, long long b) {
  if (b == 0 || a == 1) return 1;
  if (b % 2 == 0) {
    long long k = pow(a, b / 2);
    return (k * k);
  } else {
    long long k = pow(a, b / 2);
    return k * k * a;
  }
}
long long powmod(long long a, long long b, long long mod) {
  if (b == 0 || a == 1) {
    if (mod == 1)
      return 0;
    else
      return 1;
  }
  if (b % 2 == 0) {
    long long k = powmod(a, b / 2, mod);
    return (k * k) % mod;
  } else {
    long long k = powmod(a, b / 2, mod);
    return ((k * k) % mod * a) % mod;
  }
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (a > b)
    return gcd(a % b, b);
  else
    return gcd(b % a, a);
}
long long prime(long long p) {
  for (long long i = 2; i * i <= p; i++) {
    if (p % i == 0 && i < p) return 0;
  }
  return 1;
}
long long sqr(long long i) { return i * i; }
using namespace std;
signed main() {
  long long s, k;
  cin >> s >> k;
  if (k > 31) {
    vector<long long> ans;
    long long pows[35];
    pows[0] = 1;
    for (long long i = 1; i < 35; i++) pows[i] = pows[i - 1] * 2;
    for (long long i = 34; i >= 0; i--)
      if (s >= pows[i]) {
        ans.push_back(pows[i]);
        s -= pows[i];
      }
    ans.push_back(0);
    cout << ans.size() << "\n";
    for (long long i = 0; i < ans.size(); i++) cout << ans[i] << " ";
    return 0;
  }
  long long fib[100];
  for (long long i = 0; i < k; i++) fib[i] = 0;
  fib[k] = 1;
  long long ans = 0;
  for (long long i = k + 1; i < 100; i++) {
    fib[i] = 0;
    for (long long j = i - k; j <= i - 1; j++) fib[i] += fib[j];
    if (fib[i] > s) {
      ans = i;
      break;
    }
  }
  vector<long long> qq;
  for (long long i = ans; i >= 0; i--)
    if (s >= fib[i] && fib[i] != 0) {
      qq.push_back(fib[i]);
      s -= fib[i];
    }
  qq.push_back(0);
  cout << qq.size() << "\n";
  for (long long i = 0; i < qq.size(); i++) cout << qq[i] << " ";
  return 0;
}