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;
bool isprime(long long n) {
  for (long long i = sqrt(n); i > 1; i--) {
    if (n % i == 0) return false;
  }
  return true;
}
bool is_int(long double d) {
  if (d == ceil(d)) return true;
  return false;
}
long long fact(int x) {
  if (x == 0 || x == 1)
    return 1;
  else
    return x * fact(x - 1);
}
long long ncr(long long n, long long r) {
  return (fact(n) / (fact(r) * fact(n - r)));
}
long long gcd(long long n, long long m) {
  if (n % m == 0) return m;
  if (n < m) swap(n, m);
  while (m > 0) {
    n = n % m;
    swap(n, m);
  }
  return n;
}
bool isPowerOfTwo(int n) {
  if (n == 0) return false;
  return (ceil(log2(n)) == floor(log2(n)));
}
int binary_search(int x, int low, int high, int arr[]) {
  if (low == high)
    return low;
  else {
    int mid = (low + high) / 2;
    if (arr[mid] == x)
      return mid;
    else if (arr[mid] > x)
      return binary_search(x, low, mid - 1, arr);
    else
      return binary_search(x, mid + 1, high, arr);
  }
  return -1;
}
vector<int> primev;
void SieveOfEratosthenes(int n) {
  bool prime[n + 1];
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  for (int p = 2; p <= n; p++)
    if (prime[p]) primev.push_back(p);
}
int sum_of_digits(long long n) {
  int res{};
  while (n > 0) {
    res += (n % 10);
    n /= 10;
  }
  return res;
}
void solve() {
  long long n, k, i{1}, sum{};
  cin >> n >> k;
  vector<long long> v, vres;
  v.push_back(1);
  while (sum < n) {
    if (i - k - 1 >= 0) sum -= v[i - k - 1];
    sum += v[i - 1];
    v.push_back(sum);
    i++;
  }
  sum = n;
  while (sum > 0) {
    auto it = upper_bound(v.begin(), v.end(), sum);
    it--;
    if (*it == n) {
      vres.push_back(0);
    }
    vres.push_back(*it);
    sum -= *it;
  }
  cout << vres.size() << "\n";
  for (auto t : vres) cout << t << " ";
  cout << "\n";
  ;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int q = 1;
  while (q--) solve();
}