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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        EVorVMagazine solver = new EVorVMagazine();
        solver.solve(1, in, out);
        out.close();
    }

    static class EVorVMagazine {
        FFT fft = new FFT();

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            if (true) {
                int n = in.readInt();
                int k = in.readInt();
                int[] a = in.readIntArray(n);
                int[] answer = solve2(n, k, a);
                out.print(answer);
            } else {
                int n = 1000;
                int[] h = new int[n];
                for (int i = 0; i < n; i++) {
                    h[i] = 1 + i;
                }
                int k = 1000;
                int[] ans = solve2(n, k, h);
                out.print(ans);
            }
        }

        int[] solve2(int n, int k, int[] have) {
            double[] a = new double[1001];
            for (int x : have) {
                a[x] = 1;
            }
            double[] b = fft.pow(fft.compress(a), k);
            int ansSize = 0;
            for (double c : b) {
                if (c > 0.1) {
                    ansSize++;
                }
            }
            int[] ans = new int[ansSize];
            ansSize = 0;
            for (int i = 0; i < b.length; i++) {
                if (b[i] > 0.1) {
                    ans[ansSize++] = i;
                }
            }
            return ans;
        }

        class Complex {
            double real;
            double imag;

            Complex(double real, double imag) {
                this.real = real;
                this.imag = imag;
            }

            public String toString() {
                return String.format("{%.2f, %.2f}", real, imag);
            }

        }

        class FFT {
            Complex[] ws;
            Complex[] rws;
            int[][] revs;

            FFT() {
                if (false) {
                    ws = new Complex[1 << 20];
                    rws = new Complex[1 << 20];
                    for (int i = 0; i < ws.length; i++) {
                        double a = 2 * Math.PI * i / ws.length;
                        ws[i] = new Complex(Math.cos(a), Math.sin(a));
                        rws[i] = new Complex(Math.cos(-a), Math.sin(-a));
                    }
                }

                revs = new int[21][];
                for (int log = 0; log < revs.length; log++) {
                    int n = 1 << log;
                    int[] rev = revs[log] = new int[n];
                    for (int i = 1, j = -1; i < n; i++) {
                        if ((i & (i - 1)) == 0) {
                            j++;
                        }
                        rev[i] = rev[i ^ (1 << j)] | (1 << (log - 1 - j));
                    }
                }
            }

            double[] mul(double[] a, double[] b) {
                int n = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
                double[] aReal = copy(a, n);
                double[] aImag = new double[n];
                double[] bReal;
                double[] bImag;
                fft(aReal, aImag, false);
                if (a == b) {
                    bReal = aReal;
                    bImag = aImag;
                } else {
                    bReal = copy(b, n);
                    bImag = new double[n];
                    fft(bReal, bImag, false);
                }
                for (int i = 0; i < n; i++) {
                    double real = aReal[i] * bReal[i] - aImag[i] * bImag[i];
                    double imag = aReal[i] * bImag[i] + aImag[i] * bReal[i];
                    aReal[i] = real;
                    aImag[i] = imag;
                }
                fft(aReal, aImag, true);
                return compress(aReal);
            }

            double[] compress(double[] a) {
                int sz = a.length;
                while (a[sz - 1] < 0.1) {
                    sz--;
                }
                for (int i = 0; i < sz; i++) {
                    a[i] = a[i] < 0.1 ? 0 : 1;
                }
                return Arrays.copyOfRange(a, 0, sz);
            }

            double[] copy(double[] a, int n) {
                double[] b = new double[n];
                System.arraycopy(a, 0, b, 0, a.length);
                return b;
            }

            void fft(double[] real, double[] imag, boolean inv) {
                int n = real.length;
                int m = 0;
                while (1 << m < n) {
                    m++;
                }
                int[] rev = new int[n];
                for (int i = 1, j = -1; i < n; i++) {
                    if ((i & (i - 1)) == 0) {
                        j++;
                    }
                    rev[i] = rev[i ^ (1 << j)] | (1 << (m - 1 - j));
                }
                for (int i = 0; i < n; i++) {
                    if (i > rev[i]) {
                        double t = real[i];
                        real[i] = real[rev[i]];
                        real[rev[i]] = t;
                        t = imag[i];
                        imag[i] = imag[rev[i]];
                        imag[rev[i]] = t;
                    }
                }

                for (int len = 1; len < n; len <<= 1) {
                    double w = Math.PI / len;
                    if (inv) {
                        w = -w;
                    }
                    double sinw = Math.sin(w);
                    double cosw = Math.cos(w);
                    for (int i = 0; i < n; i += len * 2) {
                        double wr = 1;
                        double wi = 0;
                        for (int j = 0; j < len; j++) {
                            double real1 = real[i + j];
                            double imag1 = imag[i + j];
                            double real2 = real[i + j + len];
                            double imag2 = imag[i + j + len];

                            double real3 = real2 * wr - imag2 * wi;
                            double imag3 = real2 * wi + imag2 * wr;

                            real[i + j] = real1 + real3;
                            imag[i + j] = imag1 + imag3;
                            real[i + j + len] = real1 - real3;
                            imag[i + j + len] = imag1 - imag3;

                            double nextwr = wr * cosw - wi * sinw;
                            double nextwi = wr * sinw + wi * cosw;
                            wr = nextwr;
                            wi = nextwi;
                        }
                    }
                }

                if (inv) {
                    for (int i = 0; i < n; i++) {
                        real[i] /= n;
                        imag[i] /= n;
                    }
                }
            }

            double[] pow(double[] a, int p) {
                if (p == 1) {
                    return a;
                }
                double[] b = pow(a, p / 2);
                b = mul(b, b);
                if (p % 2 == 1) {
                    b = mul(b, a);
                }
                return b;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = readInt();
            }
            return array;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(array[i]);
            }
        }

        public void close() {
            writer.close();
        }

    }
}

