#include <bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
inline void smax(int &x, int y) { x = max(x, y); }
inline void smin(int &x, int y) { x = min(x, y); }
ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a % b)); }
const double PI = acos(-1.0l);
vector<long long> rev;
vector<complex<double> > omega;
void calc_rev(long long n, long long log_n) {
  rev.resize(n);
  omega.resize(n);
  for (long long i = 0; i < n; i++) {
    rev[i] = 0;
    for (long long j = 0; j < log_n; j++) {
      if ((i >> j) & 1) rev[i] |= 1 << (log_n - j - 1);
    }
  }
}
void fft(vector<complex<double> > &A, long long n, bool invert) {
  for (long long i = 0; i < n; i++) {
    if (i < rev[i]) swap(A[i], A[rev[i]]);
  }
  for (long long len = 2; len <= n; len <<= 1) {
    double ang = 2 * PI / len * (invert ? -1 : +1);
    long long half = (len >> 1);
    complex<double> curomega(cos(ang), sin(ang));
    omega[0] = complex<double>(1, 0);
    for (long long i = 1; i < half; i++) omega[i] = omega[i - 1] * curomega;
    for (long long i = 0; i < n; i += len) {
      complex<double> t;
      long long pu = i, pv = i + half, pu_end = i + half, pw = 0;
      for (; pu != pu_end; pu++, pv++, pw++) {
        t = A[pv] * omega[pw];
        A[pv] = A[pu] - t;
        A[pu] += t;
      }
    }
  }
  if (invert)
    for (long long i = 0; i < n; i++) A[i] /= n;
}
void multiply(long long n, vector<complex<double> > &A,
              vector<complex<double> > &B, vector<long long> &C) {
  fft(A, n, false);
  fft(B, n, false);
  for (long long i = 0; i < n; i++) A[i] *= B[i];
  fft(A, n, true);
  for (long long i = 0; i < n; i++) {
    C[i] = (long long)(A[i].real() + 0.5);
    C[i] = min(C[i], 1LL);
  }
}
void Solve(long long n, vector<long long> &coeffA, vector<long long> &coeffB,
           vector<long long> &result) {
  vector<complex<double> > A(n), B(n);
  for (long long i = 0; i < n; i++) A[i] = coeffA[i];
  for (long long i = 0; i < n; i++) B[i] = coeffB[i];
  multiply(n, A, B, result);
}
void do_FFT(vector<long long> &A, vector<long long> &B,
            vector<long long> &result) {
  long long n = 1, bits = 0;
  while (n < 2 * A.size() || n < 2 * B.size()) n <<= 1, bits++;
  result.resize(n, 0);
  calc_rev(n, bits);
  vector<long long> tempA(A.begin(), A.end());
  vector<long long> tempB(B.begin(), B.end());
  tempA.resize(n);
  tempB.resize(n);
  Solve(n, tempA, tempB, result);
}
vector<ll> polpow(vector<ll> &arr, long long k) {
  vector<ll> sol;
  while (k > 0) {
    if (k % 2) {
      if (sol.size() == 0)
        for (__typeof(arr.size()) i = (0) - ((0) > (arr.size()));
             i != (arr.size()) - ((0) > (arr.size()));
             i += 1 - 2 * ((0) > (arr.size())))
          sol.push_back(arr[i]);
      else
        do_FFT(sol, arr, sol);
    }
    do_FFT(arr, arr, arr);
    k = k / 2;
  }
  return sol;
}
int32_t main() {
  long long n, k;
  cin >> n >> k;
  vector<long long> v(n);
  for (__typeof(n) i = (0) - ((0) > (n)); i != (n) - ((0) > (n));
       i += 1 - 2 * ((0) > (n)))
    cin >> v[i];
  vector<ll> arr(1001);
  for (__typeof(n) i = (0) - ((0) > (n)); i != (n) - ((0) > (n));
       i += 1 - 2 * ((0) > (n))) {
    arr[v[i]] = 1;
  }
  while (arr.back() == 0) {
    arr.pop_back();
  }
  vector<ll> res = polpow(arr, k);
  for (__typeof(res.size()) i = (1) - ((1) > (res.size()));
       i != (res.size()) - ((1) > (res.size()));
       i += 1 - 2 * ((1) > (res.size()))) {
    if (res[i] > 0) cout << i << " ";
  }
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
inline void smax(int &x, int y) { x = max(x, y); }
inline void smin(int &x, int y) { x = min(x, y); }
ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a % b)); }
const double PI = acos(-1.0l);
vector<long long> rev;
vector<complex<double> > omega;
void calc_rev(long long n, long long log_n) {
  rev.resize(n);
  omega.resize(n);
  for (long long i = 0; i < n; i++) {
    rev[i] = 0;
    for (long long j = 0; j < log_n; j++) {
      if ((i >> j) & 1) rev[i] |= 1 << (log_n - j - 1);
    }
  }
}
void fft(vector<complex<double> > &A, long long n, bool invert) {
  for (long long i = 0; i < n; i++) {
    if (i < rev[i]) swap(A[i], A[rev[i]]);
  }
  for (long long len = 2; len <= n; len <<= 1) {
    double ang = 2 * PI / len * (invert ? -1 : +1);
    long long half = (len >> 1);
    complex<double> curomega(cos(ang), sin(ang));
    omega[0] = complex<double>(1, 0);
    for (long long i = 1; i < half; i++) omega[i] = omega[i - 1] * curomega;
    for (long long i = 0; i < n; i += len) {
      complex<double> t;
      long long pu = i, pv = i + half, pu_end = i + half, pw = 0;
      for (; pu != pu_end; pu++, pv++, pw++) {
        t = A[pv] * omega[pw];
        A[pv] = A[pu] - t;
        A[pu] += t;
      }
    }
  }
  if (invert)
    for (long long i = 0; i < n; i++) A[i] /= n;
}
void multiply(long long n, vector<complex<double> > &A,
              vector<complex<double> > &B, vector<long long> &C) {
  fft(A, n, false);
  fft(B, n, false);
  for (long long i = 0; i < n; i++) A[i] *= B[i];
  fft(A, n, true);
  for (long long i = 0; i < n; i++) {
    C[i] = (long long)(A[i].real() + 0.5);
    C[i] = min(C[i], 1LL);
  }
}
void Solve(long long n, vector<long long> &coeffA, vector<long long> &coeffB,
           vector<long long> &result) {
  vector<complex<double> > A(n), B(n);
  for (long long i = 0; i < n; i++) A[i] = coeffA[i];
  for (long long i = 0; i < n; i++) B[i] = coeffB[i];
  multiply(n, A, B, result);
}
void do_FFT(vector<long long> &A, vector<long long> &B,
            vector<long long> &result) {
  long long n = 1, bits = 0;
  while (n < 2 * A.size() || n < 2 * B.size()) n <<= 1, bits++;
  result.resize(n, 0);
  calc_rev(n, bits);
  vector<long long> tempA(A.begin(), A.end());
  vector<long long> tempB(B.begin(), B.end());
  tempA.resize(n);
  tempB.resize(n);
  Solve(n, tempA, tempB, result);
}
vector<ll> polpow(vector<ll> &arr, long long k) {
  vector<ll> sol;
  while (k > 0) {
    if (k % 2) {
      if (sol.size() == 0)
        for (__typeof(arr.size()) i = (0) - ((0) > (arr.size()));
             i != (arr.size()) - ((0) > (arr.size()));
             i += 1 - 2 * ((0) > (arr.size())))
          sol.push_back(arr[i]);
      else
        do_FFT(sol, arr, sol);
    }
    do_FFT(arr, arr, arr);
    k = k / 2;
  }
  return sol;
}
int32_t main() {
  long long n, k;
  cin >> n >> k;
  vector<long long> v(n);
  for (__typeof(n) i = (0) - ((0) > (n)); i != (n) - ((0) > (n));
       i += 1 - 2 * ((0) > (n)))
    cin >> v[i];
  vector<ll> arr(1001);
  for (__typeof(n) i = (0) - ((0) > (n)); i != (n) - ((0) > (n));
       i += 1 - 2 * ((0) > (n))) {
    arr[v[i]] = 1;
  }
  while (arr.back() == 0) {
    arr.pop_back();
  }
  vector<ll> res = polpow(arr, k);
  for (__typeof(res.size()) i = (1) - ((1) > (res.size()));
       i != (res.size()) - ((1) > (res.size()));
       i += 1 - 2 * ((1) > (res.size()))) {
    if (res[i] > 0) cout << i << " ";
  }
}

```