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.*;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class A implements Runnable {

    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok = new StringTokenizer("");

    private void init() throws FileNotFoundException {
        Locale.setDefault(Locale.US);
        String fileName = "";
        if (ONLINE_JUDGE && fileName.isEmpty()) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }
        }
    }

    String readString() {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() {
        return Integer.parseInt(readString());
    }

    long readLong() {
        return Long.parseLong(readString());
    }

    double readDouble() {
        return Double.parseDouble(readString());
    }

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

    public static void main(String[] args) {
        //new Thread(null, new A(), "", 128 * (1L << 20)).start();
        new A().run();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    @Override
    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            init();
            solve();
            out.close();
            time();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

//    class Complex {
//        double x, y;
//
//        public Complex(double x, double y) {
//            this.x = x;
//            this.y = y;
//        }
//
//        Complex add(Complex other) {
//            return new Complex(x + other.x, y + other.y);
//        }
//
//        Complex sub(Complex other) {
//            return new Complex(x - other.x, y - other.y);
//        }
//
//        Complex multiply(Complex other) {
//            return new Complex(x * other.x - y * other.y, x * other.y + y * other.x);
//        }
//    }

    void fft(double[] a, double[] ai, boolean invert) {
        int n = a.length;
        if (n == 1) {
            return;
        }
        double[] a0 = new double[n / 2];
        double[] a0i = new double[n / 2];

        double[] a1 = new double[n / 2];
        double[] a1i = new double[n / 2];

        for (int i = 0, j = 0; i < n; i += 2, j++) {
            a0[j] = a[i];
            a0i[j] = ai[i];
            a1[j] = a[i + 1];
            a1i[j] = ai[i + 1];
        }
        fft(a0, a0i, invert);
        fft(a1, a1i, invert);

        double angle = 2 * Math.PI / n * (invert ? -1 : 1);
        double w = 1.0;
        double wi = 0;
        double wn = Math.cos(angle);
        double wni = Math.sin(angle);

        for (int i = 0; i < n / 2; i++) {
            double y = w * a1[i] - wi * a1i[i];
            double yi = w * a1i[i] + wi * a1[i];
            a[i] = a0[i] + y;
            ai[i] = a0i[i] + yi;

            a[i + n / 2] = a0[i] - y;
            ai[i + n / 2] = a0i[i] - yi;

            if (invert) {
                a[i] /= 2;
                ai[i] /= 2;
                a[i + n / 2] /= 2;
                ai[i + n / 2] /= 2;
            }

            double _w =  w * wn - wi * wni;
            double _wi =  wi * wn + w * wni;

            w = _w;
            wi = _wi;
        }
    }

    int[] multiply(int[] a, int[] b) {
        int n = 1;

        boolean square = a == b;

        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) a[i] = 1;
        }
        for (int i = 0; i < b.length; i++) {
            if (b[i] != 0) b[i] = 1;
        }

        int initSize = Math.max(a.length, b.length);

        int sizeA = a.length;
        int sizeB = b.length;
        while (sizeA > 0 && a[sizeA - 1] == 0) {
            sizeA--;
        }
        while (sizeB > 0 && b[sizeB - 1] == 0) sizeB--;

        a = Arrays.copyOf(a, sizeA);
        b = Arrays.copyOf(b, sizeB);

        while (a.length + b.length > n) {
            n <<= 1;
        }
        double[] ca = new double[n];
        double[] cai = new double[n];
        double[] cb = new double[n];
        double[] cbi = new double[n];
        for (int i = 0; i < n; i++) {
            if (i < a.length) {
                ca[i] = a[i];
            }
            if (i < b.length) {
                cb[i] = b[i];
            }
        }
        fft(ca, cai, false);
        if (square) {
            cb = ca;
            cbi = cai;
        } else {
            fft(cb, cbi, false);
        }
        for (int i = 0; i < n; i++) {
            double _ca = ca[i] * cb[i] - cai[i] * cbi[i];
            double _cai = ca[i] * cbi[i] + cai[i] * cb[i];
            ca[i] = _ca;
            cai[i] = _cai;
        }
        fft(ca, cai, true);
        int[] res = new int[initSize];
        for (int i = 0; i < Math.min(initSize, n); i++) {
            res[i] = (int) (ca[i] + 0.5);
        }
        return res;
    }

    int[] binPow(int[] a, int pow) {
        int n = a.length;
        int[] res = new int[n];
        res[0] = 1;
        while (pow > 0) {
            if (pow % 2 == 1) {
                res = multiply(res, a);
            }
            a = multiply(a, a);
            pow >>= 1;
        }
        return res;
    }

    private void solve() throws IOException {
        int n = readInt();
        int k = readInt();

        int[] count = new int[1001 * 1001];
        for (int i = 0; i < n; i++) {
            count[readInt()] = 1;
        }

        int[] res = binPow(count, k);
        for (int i = 1; i <= 1000 * 1001; i++) {
            if (res[i] != 0) {
                out.println(i + " ");
            }
        }
    }
}