#include <bits/stdc++.h>
#pragma GCC optimize("-O2")
using namespace std;
void err(istream_iterator<string> it) { cerr << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\t";
  err(++it, args...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &c, pair<T1, T2> &v) {
  c << "(" << v.first << "," << v.second << ")";
  return c;
}
template <template <class...> class TT, class... T>
ostream &operator<<(ostream &out, TT<T...> &c) {
  out << "{ ";
  for (auto &x : c) out << x << " ";
  out << "}";
  return out;
}
int t, n, m, k, x, y, w;
template <long long Mod, long long root_pw, long long primitive>
struct NTT {
  inline long long powm(long long x, long long pw) {
    x %= Mod;
    if (abs(pw) > Mod - 1) pw %= (Mod - 1);
    if (pw < 0) pw += Mod - 1;
    long long res = 1;
    while (pw) {
      if (pw & 1LL) res = (res * x) % Mod;
      pw >>= 1;
      x = (x * x) % Mod;
    }
    return res;
  }
  inline long long inv(long long x) { return powm(x, Mod - 2); }
  long long root, root_1;
  NTT() {
    root = powm(primitive, (Mod - 1) / root_pw);
    root_1 = inv(root);
  }
  void ntt(vector<long long> &a, bool invert) {
    int n = a.size();
    for (long long i = 1, j = 0; i < n; i++) {
      long long bit = n >> 1;
      for (; j & bit; bit >>= 1) j ^= bit;
      j ^= bit;
      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 = 0; j < len / 2; j++) {
          long long u = a[i + j], v = a[i + j + len / 2] * w % Mod;
          a[i + j] = u + v < Mod ? u + v : u + v - Mod;
          a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + Mod;
          w = w * wlen % Mod;
        }
      }
    }
    if (invert) {
      long long n_1 = inv(n);
      for (long long &x : a) x = x * n_1 % Mod;
    }
  }
  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());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    point(fa, 1, n);
    point(fb, 1, n);
    for (int i = 0; i < n; ++i) {
      fa[i] = fa[i] * fb[i] % Mod;
    }
    coef(fa, 1);
    return fa;
  }
  void point(vector<long long> &A, bool not_pow = 1, int atleast = -1) {
    if (not_pow) {
      if (atleast == -1) {
        atleast = 1;
        while (atleast < A.size()) atleast <<= 1;
      }
      A.resize(atleast, 0);
    }
    ntt(A, 0);
  }
  void coef(vector<long long> &A, bool reduce = 1) {
    ntt(A, 1);
    if (reduce)
      while (A.size() and A.back() == 0) A.pop_back();
  }
  void point_power(vector<long long> &A, long long k) {
    for (long long &x : A) x = powm(x, k);
  }
  void coef_power(vector<long long> &A, long long k) {
    point(A);
    point_power(A, k);
    coef(A);
  }
  vector<long long> power(vector<long long> &a, long long p) {
    vector<long long> res;
    res.push_back(1);
    while (p) {
      if (p & 1) res = multiply(res, a);
      a = multiply(a, a);
      p /= 2;
    }
    return res;
  }
};
const int mod = 469762049;
NTT<mod, 1 << 20, 3> ntt;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  vector<long long> a((1 << 20), 0);
  for (int i = 0; i < n; ++i) {
    cin >> x;
    a[x] = 1;
  }
  ntt.coef_power(a, k);
  for (int i = 0; i < a.size(); ++i)
    if (a[i] != 0) cout << i << " ";
  return 0;
}

### Prompt

Your challenge is to write 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>
#pragma GCC optimize("-O2")
using namespace std;
void err(istream_iterator<string> it) { cerr << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\t";
  err(++it, args...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &c, pair<T1, T2> &v) {
  c << "(" << v.first << "," << v.second << ")";
  return c;
}
template <template <class...> class TT, class... T>
ostream &operator<<(ostream &out, TT<T...> &c) {
  out << "{ ";
  for (auto &x : c) out << x << " ";
  out << "}";
  return out;
}
int t, n, m, k, x, y, w;
template <long long Mod, long long root_pw, long long primitive>
struct NTT {
  inline long long powm(long long x, long long pw) {
    x %= Mod;
    if (abs(pw) > Mod - 1) pw %= (Mod - 1);
    if (pw < 0) pw += Mod - 1;
    long long res = 1;
    while (pw) {
      if (pw & 1LL) res = (res * x) % Mod;
      pw >>= 1;
      x = (x * x) % Mod;
    }
    return res;
  }
  inline long long inv(long long x) { return powm(x, Mod - 2); }
  long long root, root_1;
  NTT() {
    root = powm(primitive, (Mod - 1) / root_pw);
    root_1 = inv(root);
  }
  void ntt(vector<long long> &a, bool invert) {
    int n = a.size();
    for (long long i = 1, j = 0; i < n; i++) {
      long long bit = n >> 1;
      for (; j & bit; bit >>= 1) j ^= bit;
      j ^= bit;
      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 = 0; j < len / 2; j++) {
          long long u = a[i + j], v = a[i + j + len / 2] * w % Mod;
          a[i + j] = u + v < Mod ? u + v : u + v - Mod;
          a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + Mod;
          w = w * wlen % Mod;
        }
      }
    }
    if (invert) {
      long long n_1 = inv(n);
      for (long long &x : a) x = x * n_1 % Mod;
    }
  }
  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());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    point(fa, 1, n);
    point(fb, 1, n);
    for (int i = 0; i < n; ++i) {
      fa[i] = fa[i] * fb[i] % Mod;
    }
    coef(fa, 1);
    return fa;
  }
  void point(vector<long long> &A, bool not_pow = 1, int atleast = -1) {
    if (not_pow) {
      if (atleast == -1) {
        atleast = 1;
        while (atleast < A.size()) atleast <<= 1;
      }
      A.resize(atleast, 0);
    }
    ntt(A, 0);
  }
  void coef(vector<long long> &A, bool reduce = 1) {
    ntt(A, 1);
    if (reduce)
      while (A.size() and A.back() == 0) A.pop_back();
  }
  void point_power(vector<long long> &A, long long k) {
    for (long long &x : A) x = powm(x, k);
  }
  void coef_power(vector<long long> &A, long long k) {
    point(A);
    point_power(A, k);
    coef(A);
  }
  vector<long long> power(vector<long long> &a, long long p) {
    vector<long long> res;
    res.push_back(1);
    while (p) {
      if (p & 1) res = multiply(res, a);
      a = multiply(a, a);
      p /= 2;
    }
    return res;
  }
};
const int mod = 469762049;
NTT<mod, 1 << 20, 3> ntt;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  vector<long long> a((1 << 20), 0);
  for (int i = 0; i < n; ++i) {
    cin >> x;
    a[x] = 1;
  }
  ntt.coef_power(a, k);
  for (int i = 0; i < a.size(); ++i)
    if (a[i] != 0) cout << i << " ";
  return 0;
}

```