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 int sum() { return 0; }
template <typename T, typename... Args>
T sum(T a, Args... args) {
  return a + sum(args...);
}
template <typename T>
class Sieve {
 public:
  vector<T> primes;
  vector<bool> is_prime;
  Sieve(int MAX = 1000000) {
    is_prime.resize(MAX + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long int i = 2; i * i <= MAX; i++)
      if (is_prime[i])
        for (long long int j = i * i; j <= MAX; j += i) is_prime[j] = false;
    for (long long int i = 2; i <= MAX; i++)
      if (is_prime[i]) primes.push_back(i);
  }
};
template <typename T>
vector<vector<T>> matmul(const vector<vector<T>>& a,
                         const vector<vector<T>>& b) {
  int n = a.size(), m = b[0].size(), k = b.size();
  vector<vector<T>> c(n, vector<T>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int l = 0; l < k; l++) c[i][j] += (a[i][k] * b[k][j]);
    }
  }
  return c;
}
template <typename T>
T extended_euclid(T a, T b, vector<T>& X) {
  if (b == 0) {
    X = {1, 0};
    return a;
  } else {
    T g = extended_euclid(b, a % b, X);
    vector<vector<T>> G = {{0LL, 1LL}, {1LL, -(a / b)}};
    X = matmul<T>(G, X);
    return g;
  }
}
template <typename T>
bool isPrime(T n) {
  if (n <= 1)
    return false;
  else if (n == 2 || n == 3)
    return true;
  else if (n % 2 == 0 || n % 3 == 0)
    return false;
  T x = 5;
  T p = 2;
  while (x * x <= n) {
    if (n % x == 0) return true;
    x += p;
    p = 6 - p;
  }
  return true;
}
long long int binpow(long long int x, long long int n,
                     long long int mod = 1000000007) {
  long long int ans = 1;
  x = x % mod;
  while (n >= 1) {
    if (n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return ans;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
template <typename T>
class Graph {
 public:
  int n;
  vector<vector<T>> adj;
  bool directed;
  Graph(int n, bool directed = false) {
    this->n = n;
    adj.resize(n + 1);
    this->directed = directed;
  }
  void add_edge(int u, int v) {
    adj[u].push_back(v);
    if (!directed) adj[v].push_back(u);
  }
  void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    if (!directed) adj[v].push_back({u, w});
  }
};
class DisjointSets {
 public:
  int n;
  vector<int> parent;
  vector<int> rank;
  vector<int> sz;
  DisjointSets(int n, bool Rank = true) {
    this->n = n;
    parent.resize(n + 1, 0);
    iota(parent.begin(), parent.end(), 0);
    (Rank ? rank.resize(n + 1, 1) : sz.resize(n + 1, 1));
  }
  int find(int i) {
    if (i != parent[i]) parent[i] = find(parent[i]);
    return parent[i];
  }
  void UnionByRank(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    if (rank[i] < rank[j]) swap(i, j);
    parent[j] = i;
    rank[i] += rank[j];
  }
  void UnionBySize(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    if (sz[i] < sz[j]) swap(i, j);
    parent[j] = i;
    sz[i] += sz[j];
  }
};
template <typename T>
class SegmentTree {
 public:
  vector<T> t;
  int n, H;
  void init(int n) {
    this->n = n;
    t.resize(2 * n);
    this->H = sizeof(int) * 8 - __builtin_clz(n);
  }
  void build() {
    for (int i = n - 1; i > 0; i--) t[i] = t[i << 1] + t[(i << 1) | 1];
  }
  void update(int pos, T val) {
    for (t[pos += n] += val; pos > 1; pos >>= 1)
      t[pos >> 1] = t[pos] + t[pos ^ 1];
  }
  T query(int l, int r) {
    T res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};
bool isSubsequenceString(string x, string y) {
  int i = 0, j = 0;
  while (i < x.length() && j < y.length()) x[i] == y[j] ? i++, j++ : i++;
  return (j == y.length());
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int s, k;
  cin >> s >> k;
  vector<long long int> f = {0, 1};
  f.push_back(1);
  for (int i = 2;; i++) {
    if (i <= k)
      f.push_back(f.back() * 2);
    else
      f.push_back(2 * f.back() - f[f.size() - k - 1]);
    if (f.back() >= s) break;
  }
  reverse(f.begin(), f.end());
  vector<long long int> ans;
  for (auto num : f) {
    while (num <= s && num != 0) {
      ans.push_back(num);
      s -= num;
    }
  }
  if (ans.size() == 1) ans.push_back(0);
  cout << ans.size() << "\n";
  for (auto num : ans) cout << num << " ";
  cout << "\n";
}