#include <bits/stdc++.h>
using namespace std;
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T first, char end = 0);
inline void writeChar(int first);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T first = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') first = first * 10 + c - '0', c = getChar();
  return s == 1 ? first : -first;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int first) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = first;
}
template <class T>
inline void writeInt(T first, char end) {
  if (first < 0) writeChar('-'), first = -first;
  char s[24];
  int n = 0;
  while (first || !n) s[n++] = '0' + first % 10, first /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
struct cp {
  double first, second;
  double real(void) { return first; }
  double imag(void) { return second; }
  cp(void) { first = second = 0; }
  cp(double first, double second) : first(first), second(second) {}
  cp(double first) : first(first), second(0) {}
};
cp operator+(cp a, cp b) { return cp(a.first + b.first, a.second + b.second); }
cp operator-(cp a, cp b) { return cp(a.first - b.first, a.second - b.second); }
void operator+=(cp &a, cp b) { a = a + b; }
void operator-=(cp &a, cp b) { a = a - b; }
cp operator*(cp a, cp b) {
  return cp(a.first * b.first - a.second * b.second,
            a.first * b.second + a.second * b.first);
}
void operator*=(cp &a, cp b) { a = a * b; }
cp operator/(cp a, double b) { return cp(a.first / b, a.second / b); }
void operator/=(cp &a, double b) { a = a / b; }
struct cpi {
  long long first, second;
  cpi(void) { first = second = 0; }
  cpi(long long first) : first(first), second(0) {}
  cpi(long long first, long long second) : first(first), second(second) {}
};
cpi operator+(cpi a, cpi b) {
  return cpi(a.first + b.first, a.second + b.second);
}
void operator+=(cpi &a, cpi b) { a = a + b; }
cpi operator-(cpi a, cpi b) {
  return cpi(a.first - b.first, a.second - b.second);
}
void operator-=(cpi &a, cpi b) { a = a + b; }
cpi operator*(cpi a, cpi b) {
  return cpi(a.first * b.first - a.second * b.second,
             a.first * b.second + a.second * b.first);
}
void operator*=(cpi &a, cpi b) { a = a * b; }
cpi operator/(cpi a, long long b) { return cpi(a.first / b, a.second / b); }
void operator/=(cpi &a, long long b) { a = a / b; }
const auto pi = acos(-1);
int Log[1 << 21];
const int N = 1 << 20;
void fft(vector<cp> &s, int n, int ok) {
  const int lg = Log[n] - 1;
  assert((1 << Log[n]) == n);
  auto rev = [&](int first) {
    int ans = 0;
    for (int k = 0; k <= lg; ++k)
      if ((first >> k) & 1) ans += 1 << (lg - k);
    return ans;
  };
  for (int i = 0; i < n; ++i)
    if (i < rev(i)) swap(s[i], s[rev(i)]);
  for (int len = 2; len <= n; len <<= 1) {
    const auto ang = 2 * pi * ok / len;
    const auto W = cp(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      cp w = cp(1, 0);
      for (int j = 0; j < len / 2; ++j) {
        const cp vv = s[i + j + (len / 2)] * w;
        const cp uu = s[i + j];
        s[i + j] = uu + vv;
        s[i + j + (len / 2)] = uu - vv;
        w *= W;
      }
    }
  }
  if (ok == -1)
    for (int i = 0; i < n; ++i) s[i] /= n;
}
void FFT(const vector<bool> &a, const vector<bool> &b, vector<bool> &c) {
  vector<cp> A(a.begin(), a.end()), B(b.begin(), b.end());
  int n = max(a.size(), b.size()) * 2;
  A.resize(n);
  B.resize(n);
  fft(A, n, 1);
  fft(B, n, 1);
  for (int i = 0; i < n; ++i) A[i] *= B[i];
  fft(A, n, -1);
  c.clear();
  for (int i = 0; i < n; ++i) c.push_back(!!(int)(A[i].real() + 0.5));
}
int main(void) {
  srand(time(0));
  cout << fixed << setprecision(7);
  cerr << fixed << setprecision(7);
  int n, k;
  for (int i = 2; i < (1 << 21); ++i) Log[i] = Log[i / 2] + 1;
  n = readInt();
  k = readInt();
  vector<bool> s(1024, 0);
  while (n--) {
    int v = readInt();
    s[v] = 1;
  }
  vector<bool> ans;
  ans.push_back(1);
  while (k) {
    if (k & 1) FFT(ans, s, ans);
    FFT(s, s, s);
    k /= 2;
  }
  n = ans.size();
  int cnt = accumulate(ans.begin(), ans.end(), 0);
  for (int i = 0; i < n; ++i)
    if (ans[i]) writeInt(i, " \n"[(--cnt) == 0]);
  cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms"
       << '\n';
  return 0;
}

### 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;
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T first, char end = 0);
inline void writeChar(int first);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T first = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') first = first * 10 + c - '0', c = getChar();
  return s == 1 ? first : -first;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int first) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = first;
}
template <class T>
inline void writeInt(T first, char end) {
  if (first < 0) writeChar('-'), first = -first;
  char s[24];
  int n = 0;
  while (first || !n) s[n++] = '0' + first % 10, first /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
struct cp {
  double first, second;
  double real(void) { return first; }
  double imag(void) { return second; }
  cp(void) { first = second = 0; }
  cp(double first, double second) : first(first), second(second) {}
  cp(double first) : first(first), second(0) {}
};
cp operator+(cp a, cp b) { return cp(a.first + b.first, a.second + b.second); }
cp operator-(cp a, cp b) { return cp(a.first - b.first, a.second - b.second); }
void operator+=(cp &a, cp b) { a = a + b; }
void operator-=(cp &a, cp b) { a = a - b; }
cp operator*(cp a, cp b) {
  return cp(a.first * b.first - a.second * b.second,
            a.first * b.second + a.second * b.first);
}
void operator*=(cp &a, cp b) { a = a * b; }
cp operator/(cp a, double b) { return cp(a.first / b, a.second / b); }
void operator/=(cp &a, double b) { a = a / b; }
struct cpi {
  long long first, second;
  cpi(void) { first = second = 0; }
  cpi(long long first) : first(first), second(0) {}
  cpi(long long first, long long second) : first(first), second(second) {}
};
cpi operator+(cpi a, cpi b) {
  return cpi(a.first + b.first, a.second + b.second);
}
void operator+=(cpi &a, cpi b) { a = a + b; }
cpi operator-(cpi a, cpi b) {
  return cpi(a.first - b.first, a.second - b.second);
}
void operator-=(cpi &a, cpi b) { a = a + b; }
cpi operator*(cpi a, cpi b) {
  return cpi(a.first * b.first - a.second * b.second,
             a.first * b.second + a.second * b.first);
}
void operator*=(cpi &a, cpi b) { a = a * b; }
cpi operator/(cpi a, long long b) { return cpi(a.first / b, a.second / b); }
void operator/=(cpi &a, long long b) { a = a / b; }
const auto pi = acos(-1);
int Log[1 << 21];
const int N = 1 << 20;
void fft(vector<cp> &s, int n, int ok) {
  const int lg = Log[n] - 1;
  assert((1 << Log[n]) == n);
  auto rev = [&](int first) {
    int ans = 0;
    for (int k = 0; k <= lg; ++k)
      if ((first >> k) & 1) ans += 1 << (lg - k);
    return ans;
  };
  for (int i = 0; i < n; ++i)
    if (i < rev(i)) swap(s[i], s[rev(i)]);
  for (int len = 2; len <= n; len <<= 1) {
    const auto ang = 2 * pi * ok / len;
    const auto W = cp(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      cp w = cp(1, 0);
      for (int j = 0; j < len / 2; ++j) {
        const cp vv = s[i + j + (len / 2)] * w;
        const cp uu = s[i + j];
        s[i + j] = uu + vv;
        s[i + j + (len / 2)] = uu - vv;
        w *= W;
      }
    }
  }
  if (ok == -1)
    for (int i = 0; i < n; ++i) s[i] /= n;
}
void FFT(const vector<bool> &a, const vector<bool> &b, vector<bool> &c) {
  vector<cp> A(a.begin(), a.end()), B(b.begin(), b.end());
  int n = max(a.size(), b.size()) * 2;
  A.resize(n);
  B.resize(n);
  fft(A, n, 1);
  fft(B, n, 1);
  for (int i = 0; i < n; ++i) A[i] *= B[i];
  fft(A, n, -1);
  c.clear();
  for (int i = 0; i < n; ++i) c.push_back(!!(int)(A[i].real() + 0.5));
}
int main(void) {
  srand(time(0));
  cout << fixed << setprecision(7);
  cerr << fixed << setprecision(7);
  int n, k;
  for (int i = 2; i < (1 << 21); ++i) Log[i] = Log[i / 2] + 1;
  n = readInt();
  k = readInt();
  vector<bool> s(1024, 0);
  while (n--) {
    int v = readInt();
    s[v] = 1;
  }
  vector<bool> ans;
  ans.push_back(1);
  while (k) {
    if (k & 1) FFT(ans, s, ans);
    FFT(s, s, s);
    k /= 2;
  }
  n = ans.size();
  int cnt = accumulate(ans.begin(), ans.end(), 0);
  for (int i = 0; i < n; ++i)
    if (ans[i]) writeInt(i, " \n"[(--cnt) == 0]);
  cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms"
       << '\n';
  return 0;
}

```