#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
const long long UP = 4e5 + 4, mod = 998244353;
template <long long Mod, long long root_pw, long long generator>
struct NTT {
  inline long long powm(long long a, long long b) {
    a %= Mod;
    b %= (Mod - 1);
    if (b < 0) b += (Mod - 1);
    long long ans = 1;
    while (b) {
      if (b & 1ll) ans = ans * a % Mod;
      b /= 2;
      a = (a * a) % Mod;
    }
    return ans;
  }
  inline long long inv(long long a) { return powm(a, Mod - 2); }
  long long root, root_1;
  NTT() {
    root = powm(generator, (Mod - 1) / root_pw);
    root_1 = inv(root);
  }
  void ntt(vector<long long> &a, bool invert) {
    int n = (int)a.size();
    for (long long i = 1, j = 0; i < n; ++i) {
      long long b = n >> 1;
      for (; j & b; b >>= 1) j ^= b;
      j ^= b;
      if (i < j) swap(a[i], a[j]);
    }
    for (long long len = 2; len <= n; len <<= 1) {
      long long wlen = invert ? root_1 : root;
      for (long long i = len; i < root_pw; i <<= 1) {
        wlen = (wlen * wlen % Mod);
      }
      for (long long i = 0; i < n; i += len) {
        long long w = 1;
        for (long long j = i; j < i + len / 2; j++) {
          long long k = j + len / 2;
          a[k] = (a[j] - w * a[k] % Mod + Mod) % Mod;
          a[j] = (2 * a[j] % Mod - a[k] + Mod) % Mod;
          w = w * wlen % Mod;
        }
      }
    }
    if (invert) {
      long long ninv = inv(n);
      for (long long i = (long long)0; i != (long long)n; i = i + 1)
        a[i] = a[i] * ninv % Mod;
    }
  }
  void extend_nnt(vector<long long> &a, bool ext = 1, long long atleast = -1) {
    if (ext) {
      if (atleast == -1) {
        atleast = 1;
        while (atleast < 1ll * (int)a.size()) atleast <<= 1;
      }
      a.resize(atleast, 0);
    }
    ntt(a, 0);
  }
  void innt(vector<long long> &a, bool reduce = 1) {
    ntt(a, 1);
    if (reduce)
      while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
  }
  void elem_power(vector<long long> &a, long long k) {
    for (auto &x : a) x = powm(x, k);
  }
  void poly_power(vector<long long> &a, long long k) {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
    long long n = 1;
    while (n < k * (int)a.size()) n <<= 1;
    extend_nnt(a, 1, n);
    elem_power(a, k);
    innt(a);
  }
  vector<long long> power(vector<long long> a, long long p) {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
    vector<long long> ans;
    ans.push_back(1);
    while (p) {
      if (p & 1) ans = multiply(ans, a);
      a = multiply(a, a);
      p /= 2;
    }
    return ans;
  }
  vector<long long> multiply(vector<long long> const &a,
                             vector<long long> const &b) {
    vector<long long> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    long long n = 1;
    while (n < 1ll * (int)a.size() + 1ll * (int)b.size()) n <<= 1;
    extend_nnt(fa, 1, n);
    extend_nnt(fb, 1, n);
    for (long long i = (long long)0; i != (long long)n; i = i + 1) {
      fa[i] = fa[i] * fb[i] % Mod;
    }
    innt(fa);
    for (int i = 0; i < fa.size(); i++) fa[i] = fa[i] > 0 ? 1 : 0;
    return fa;
  }
  void multiply_mem(vector<long long> &a, vector<long long> const &b) {
    vector<long long> fb(b.begin(), b.end());
    long long n = 1;
    while (n < 1ll * (int)a.size() + 1ll * (int)b.size()) n <<= 1;
    extend_nnt(a, 1, n);
    extend_nnt(fb, 1, n);
    for (long long i = (long long)0; i != (long long)n; i = i + 1) {
      a[i] = a[i] * fb[i] % Mod;
    }
    innt(a);
    for (int i = 0; i < a.size(); i++) a[i] = a[i] > 0 ? 1 : 0;
  }
};
NTT<mod, 1 << 20, 3> ntt;
inline long long powm(long long a, long long b, long long Mod) {
  a %= Mod;
  long long ans = 1;
  while (b) {
    if (b & 1ll) ans = (ans * a) % Mod;
    b >>= 1;
    a = a * a % Mod;
  }
  return ans;
}
inline long long inv(long long x, long long Mod) {
  return powm(x, Mod - 2, Mod);
}
long long iv[UP];
void pre() {
  for (long long i = (long long)1; i != (long long)UP; i = i + 1)
    iv[i] = inv(i, mod);
}
template <long long Mod>
class poly {
 public:
  vector<long long> a;
  poly() {}
  void reduce() {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
  }
  poly(const vector<long long> &a) : a(a) { reduce(); }
  poly operator+=(const poly &rhs) {
    a.resize(max((int)a.size(), (int)rhs.a.size()), 0);
    for (long long i = (long long)0; i != (long long)(int)rhs.a.size();
         i = i + 1) {
      a[i] += rhs.a[i];
      if (a[i] >= Mod) a[i] -= Mod;
    }
    reduce();
    return *this;
  }
  poly operator-=(const poly &rhs) {
    a.resize(max((int)a.size(), (int)rhs.a.size()), 0);
    for (long long i = (long long)0; i != (long long)(int)rhs.a.size();
         i = i + 1) {
      a[i] -= rhs.a[i];
      if (a[i] < 0) a[i] += Mod;
    }
    reduce();
    return *this;
  }
  poly operator*=(const long long &x) {
    for (auto &y : a) y = y * x % Mod;
    if (x < 0)
      for (auto &y : a)
        if (y) y += Mod;
    reduce();
    return *this;
  }
  poly operator*=(const poly &t) {
    ntt.multiply_mem(a, t.a);
    return *this;
  }
  poly operator+(const poly &t) const { return poly(*this) += t; }
  poly operator-(const poly &t) const { return poly(*this) -= t; }
  poly operator*(const poly &t) const { return poly(*this) *= t; }
  poly operator*(const long long &x) const { return poly(*this) *= x; }
  long long &operator[](int id) {
    assert(id < a.size() && id >= 0);
    return a[id];
  }
  poly mod_xk(size_t k) const {
    return vector<long long>(a.begin(), a.begin() + min(k, a.size()));
  }
  poly mul_xk(size_t k) const {
    poly ans(*this);
    ans.a.insert(ans.a.begin(), k, 0ll);
    return ans;
  }
  poly div_xk(size_t k) const {
    return vector<long long>(a.begin() + min(a.size(), k), a.end());
  }
  poly subpoly(size_t l, size_t r) const {
    return vector<long long>(a.begin() + min(l, a.size()),
                             a.begin() + min(r, a.size()));
  }
  poly deriv() const {
    vector<long long> ans;
    for (long long i = (long long)1; i != (long long)a.size(); i = i + 1)
      ans.push_back(i * a[i] % Mod);
    return ans;
  }
  poly integrat() const {
    vector<long long> ans(vector<long long>{0});
    for (long long i = (long long)0; i != (long long)a.size(); i = i + 1)
      ans.push_back(a[i] * iv[i + 1] % Mod);
    return ans;
  }
  poly inv_series(size_t n) const {
    assert(a.size() && a[0]);
    long long modiv = inv(a[0], Mod);
    poly ans({modiv});
    size_t tot = 1;
    while (tot < n) {
      poly c = (ans * mod_xk(2 * tot)).subpoly(tot, 2 * tot);
      ans -= (ans * c).mod_xk(tot).mul_xk(tot);
      tot *= 2;
    }
    return ans.mod_xk(n);
  }
  poly logs(size_t n) {
    assert(a.size() && a[0] == 1);
    return (deriv().mod_xk(n) * inv_series(n)).integrat().mod_xk(n);
  }
  poly exps(size_t n) {
    reduce();
    poly ans(vector<long long>{1});
    if ((int)a.size() == 0) return ans;
    assert(a[0] == 0);
    size_t tot = 1;
    while (tot < n) {
      poly c = ans.logs(2 * tot).div_xk(tot) - subpoly(tot, 2 * tot);
      ans -= (ans * c).mod_xk(tot).mul_xk(tot);
      tot *= 2;
    }
    return ans.mod_xk(n);
  }
  long long eval(long long x) const {
    long long ans(0);
    for (long long i = (long long)(int)a.size() - 1; i != (long long)-1;
         i = i + -1) {
      ans = ans * x % Mod;
      ans += a[i];
      if (ans >= Mod) ans -= Mod;
    }
    return ans;
  }
  poly reverse(size_t n, bool rev = 0) const {
    poly ans(*this);
    if (rev) {
      ans.a.resize(max(n, ans.a.size()));
    }
    std::reverse(ans.a.begin(), ans.a.end());
    return ans.mod_xk(n);
  }
  pair<poly, poly> divmod(const poly &b) const {
    if (a.size() < b.a.size()) return {poly(vector<long long>{0}), *this};
    int d = int(a.size()) - int(b.a.size());
    poly D = (reverse(d + 1) * b.reverse(d + 1).inv_series(d + 1))
                 .mod_xk(d + 1)
                 .reverse(d + 1, 1);
    return {D, *this - D * b};
  }
  poly operator/(const poly &t) const { return divmod(t).first; }
  poly operator%(const poly &t) const { return divmod(t).second; }
  poly pow(size_t k, size_t n) {
    reduce();
    if (a.size() == 0) return *this;
    long long lead;
    int index;
    for (long long i = (long long)0; i != (long long)(int)a.size(); i = i + 1) {
      if (a[i]) {
        lead = a[i];
        index = i;
        break;
      }
    }
    if (index * k >= n) return vector<long long>{0};
    poly t = div_xk(index) * inv(lead, Mod);
    return (((t.logs(n) * k).exps(n)) * powm(lead, k, Mod))
        .mul_xk(index * k)
        .mod_xk(n);
  }
};
vector<long long> a(1001);
int n, k, val;
void solve() {
  cin >> n >> k;
  for (long long i = (long long)0; i != (long long)n; i = i + 1) {
    cin >> val;
    a[val] = 1;
  }
  poly<mod> A(a);
  poly<mod> B(vector<long long>{1});
  while (k) {
    if (k & 1) B *= A;
    k /= 2;
    A = A * A;
  }
  B.reduce();
  for (long long i = (long long)1; i != (long long)(int)B.a.size(); i = i + 1) {
    if (B.a[i]) cout << i << " ";
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Generate a CPP solution to the following problem:

A thief made his way to a shop.

As usual he has his lucky knapsack with him. The knapsack can contain k objects. There are n kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind i is ai.

The thief is greedy, so he will take exactly k products (it's possible for some kinds to take several products of that kind).

Find all the possible total costs of products the thief can nick into his knapsack.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.

The second line contains n integers ai (1 ≤ ai ≤ 1000) — the costs of products for kinds from 1 to n.

Output

Print the only line with all the possible total costs of stolen products, separated by a space. The numbers should be printed in the ascending order.

Examples

Input

3 2
1 2 3


Output

2 3 4 5 6


Input

5 5
1 1 1 1 1


Output

5


Input

3 3
3 5 11


Output

9 11 13 15 17 19 21 25 27 33

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
const long long UP = 4e5 + 4, mod = 998244353;
template <long long Mod, long long root_pw, long long generator>
struct NTT {
  inline long long powm(long long a, long long b) {
    a %= Mod;
    b %= (Mod - 1);
    if (b < 0) b += (Mod - 1);
    long long ans = 1;
    while (b) {
      if (b & 1ll) ans = ans * a % Mod;
      b /= 2;
      a = (a * a) % Mod;
    }
    return ans;
  }
  inline long long inv(long long a) { return powm(a, Mod - 2); }
  long long root, root_1;
  NTT() {
    root = powm(generator, (Mod - 1) / root_pw);
    root_1 = inv(root);
  }
  void ntt(vector<long long> &a, bool invert) {
    int n = (int)a.size();
    for (long long i = 1, j = 0; i < n; ++i) {
      long long b = n >> 1;
      for (; j & b; b >>= 1) j ^= b;
      j ^= b;
      if (i < j) swap(a[i], a[j]);
    }
    for (long long len = 2; len <= n; len <<= 1) {
      long long wlen = invert ? root_1 : root;
      for (long long i = len; i < root_pw; i <<= 1) {
        wlen = (wlen * wlen % Mod);
      }
      for (long long i = 0; i < n; i += len) {
        long long w = 1;
        for (long long j = i; j < i + len / 2; j++) {
          long long k = j + len / 2;
          a[k] = (a[j] - w * a[k] % Mod + Mod) % Mod;
          a[j] = (2 * a[j] % Mod - a[k] + Mod) % Mod;
          w = w * wlen % Mod;
        }
      }
    }
    if (invert) {
      long long ninv = inv(n);
      for (long long i = (long long)0; i != (long long)n; i = i + 1)
        a[i] = a[i] * ninv % Mod;
    }
  }
  void extend_nnt(vector<long long> &a, bool ext = 1, long long atleast = -1) {
    if (ext) {
      if (atleast == -1) {
        atleast = 1;
        while (atleast < 1ll * (int)a.size()) atleast <<= 1;
      }
      a.resize(atleast, 0);
    }
    ntt(a, 0);
  }
  void innt(vector<long long> &a, bool reduce = 1) {
    ntt(a, 1);
    if (reduce)
      while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
  }
  void elem_power(vector<long long> &a, long long k) {
    for (auto &x : a) x = powm(x, k);
  }
  void poly_power(vector<long long> &a, long long k) {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
    long long n = 1;
    while (n < k * (int)a.size()) n <<= 1;
    extend_nnt(a, 1, n);
    elem_power(a, k);
    innt(a);
  }
  vector<long long> power(vector<long long> a, long long p) {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
    vector<long long> ans;
    ans.push_back(1);
    while (p) {
      if (p & 1) ans = multiply(ans, a);
      a = multiply(a, a);
      p /= 2;
    }
    return ans;
  }
  vector<long long> multiply(vector<long long> const &a,
                             vector<long long> const &b) {
    vector<long long> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    long long n = 1;
    while (n < 1ll * (int)a.size() + 1ll * (int)b.size()) n <<= 1;
    extend_nnt(fa, 1, n);
    extend_nnt(fb, 1, n);
    for (long long i = (long long)0; i != (long long)n; i = i + 1) {
      fa[i] = fa[i] * fb[i] % Mod;
    }
    innt(fa);
    for (int i = 0; i < fa.size(); i++) fa[i] = fa[i] > 0 ? 1 : 0;
    return fa;
  }
  void multiply_mem(vector<long long> &a, vector<long long> const &b) {
    vector<long long> fb(b.begin(), b.end());
    long long n = 1;
    while (n < 1ll * (int)a.size() + 1ll * (int)b.size()) n <<= 1;
    extend_nnt(a, 1, n);
    extend_nnt(fb, 1, n);
    for (long long i = (long long)0; i != (long long)n; i = i + 1) {
      a[i] = a[i] * fb[i] % Mod;
    }
    innt(a);
    for (int i = 0; i < a.size(); i++) a[i] = a[i] > 0 ? 1 : 0;
  }
};
NTT<mod, 1 << 20, 3> ntt;
inline long long powm(long long a, long long b, long long Mod) {
  a %= Mod;
  long long ans = 1;
  while (b) {
    if (b & 1ll) ans = (ans * a) % Mod;
    b >>= 1;
    a = a * a % Mod;
  }
  return ans;
}
inline long long inv(long long x, long long Mod) {
  return powm(x, Mod - 2, Mod);
}
long long iv[UP];
void pre() {
  for (long long i = (long long)1; i != (long long)UP; i = i + 1)
    iv[i] = inv(i, mod);
}
template <long long Mod>
class poly {
 public:
  vector<long long> a;
  poly() {}
  void reduce() {
    while ((int)a.size() > 0 && a.back() == 0) a.pop_back();
  }
  poly(const vector<long long> &a) : a(a) { reduce(); }
  poly operator+=(const poly &rhs) {
    a.resize(max((int)a.size(), (int)rhs.a.size()), 0);
    for (long long i = (long long)0; i != (long long)(int)rhs.a.size();
         i = i + 1) {
      a[i] += rhs.a[i];
      if (a[i] >= Mod) a[i] -= Mod;
    }
    reduce();
    return *this;
  }
  poly operator-=(const poly &rhs) {
    a.resize(max((int)a.size(), (int)rhs.a.size()), 0);
    for (long long i = (long long)0; i != (long long)(int)rhs.a.size();
         i = i + 1) {
      a[i] -= rhs.a[i];
      if (a[i] < 0) a[i] += Mod;
    }
    reduce();
    return *this;
  }
  poly operator*=(const long long &x) {
    for (auto &y : a) y = y * x % Mod;
    if (x < 0)
      for (auto &y : a)
        if (y) y += Mod;
    reduce();
    return *this;
  }
  poly operator*=(const poly &t) {
    ntt.multiply_mem(a, t.a);
    return *this;
  }
  poly operator+(const poly &t) const { return poly(*this) += t; }
  poly operator-(const poly &t) const { return poly(*this) -= t; }
  poly operator*(const poly &t) const { return poly(*this) *= t; }
  poly operator*(const long long &x) const { return poly(*this) *= x; }
  long long &operator[](int id) {
    assert(id < a.size() && id >= 0);
    return a[id];
  }
  poly mod_xk(size_t k) const {
    return vector<long long>(a.begin(), a.begin() + min(k, a.size()));
  }
  poly mul_xk(size_t k) const {
    poly ans(*this);
    ans.a.insert(ans.a.begin(), k, 0ll);
    return ans;
  }
  poly div_xk(size_t k) const {
    return vector<long long>(a.begin() + min(a.size(), k), a.end());
  }
  poly subpoly(size_t l, size_t r) const {
    return vector<long long>(a.begin() + min(l, a.size()),
                             a.begin() + min(r, a.size()));
  }
  poly deriv() const {
    vector<long long> ans;
    for (long long i = (long long)1; i != (long long)a.size(); i = i + 1)
      ans.push_back(i * a[i] % Mod);
    return ans;
  }
  poly integrat() const {
    vector<long long> ans(vector<long long>{0});
    for (long long i = (long long)0; i != (long long)a.size(); i = i + 1)
      ans.push_back(a[i] * iv[i + 1] % Mod);
    return ans;
  }
  poly inv_series(size_t n) const {
    assert(a.size() && a[0]);
    long long modiv = inv(a[0], Mod);
    poly ans({modiv});
    size_t tot = 1;
    while (tot < n) {
      poly c = (ans * mod_xk(2 * tot)).subpoly(tot, 2 * tot);
      ans -= (ans * c).mod_xk(tot).mul_xk(tot);
      tot *= 2;
    }
    return ans.mod_xk(n);
  }
  poly logs(size_t n) {
    assert(a.size() && a[0] == 1);
    return (deriv().mod_xk(n) * inv_series(n)).integrat().mod_xk(n);
  }
  poly exps(size_t n) {
    reduce();
    poly ans(vector<long long>{1});
    if ((int)a.size() == 0) return ans;
    assert(a[0] == 0);
    size_t tot = 1;
    while (tot < n) {
      poly c = ans.logs(2 * tot).div_xk(tot) - subpoly(tot, 2 * tot);
      ans -= (ans * c).mod_xk(tot).mul_xk(tot);
      tot *= 2;
    }
    return ans.mod_xk(n);
  }
  long long eval(long long x) const {
    long long ans(0);
    for (long long i = (long long)(int)a.size() - 1; i != (long long)-1;
         i = i + -1) {
      ans = ans * x % Mod;
      ans += a[i];
      if (ans >= Mod) ans -= Mod;
    }
    return ans;
  }
  poly reverse(size_t n, bool rev = 0) const {
    poly ans(*this);
    if (rev) {
      ans.a.resize(max(n, ans.a.size()));
    }
    std::reverse(ans.a.begin(), ans.a.end());
    return ans.mod_xk(n);
  }
  pair<poly, poly> divmod(const poly &b) const {
    if (a.size() < b.a.size()) return {poly(vector<long long>{0}), *this};
    int d = int(a.size()) - int(b.a.size());
    poly D = (reverse(d + 1) * b.reverse(d + 1).inv_series(d + 1))
                 .mod_xk(d + 1)
                 .reverse(d + 1, 1);
    return {D, *this - D * b};
  }
  poly operator/(const poly &t) const { return divmod(t).first; }
  poly operator%(const poly &t) const { return divmod(t).second; }
  poly pow(size_t k, size_t n) {
    reduce();
    if (a.size() == 0) return *this;
    long long lead;
    int index;
    for (long long i = (long long)0; i != (long long)(int)a.size(); i = i + 1) {
      if (a[i]) {
        lead = a[i];
        index = i;
        break;
      }
    }
    if (index * k >= n) return vector<long long>{0};
    poly t = div_xk(index) * inv(lead, Mod);
    return (((t.logs(n) * k).exps(n)) * powm(lead, k, Mod))
        .mul_xk(index * k)
        .mod_xk(n);
  }
};
vector<long long> a(1001);
int n, k, val;
void solve() {
  cin >> n >> k;
  for (long long i = (long long)0; i != (long long)n; i = i + 1) {
    cin >> val;
    a[val] = 1;
  }
  poly<mod> A(a);
  poly<mod> B(vector<long long>{1});
  while (k) {
    if (k & 1) B *= A;
    k /= 2;
    A = A * A;
  }
  B.reduce();
  for (long long i = (long long)1; i != (long long)(int)B.a.size(); i = i + 1) {
    if (B.a[i]) cout << i << " ";
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

```