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.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class e2 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		long[] freqs = new long[1001];
		for(int i=0;i<n;i++)
			freqs[scan.nextInt()] = 1; // inf amount of each, all we care about is if we have at least 1
		freqs = fastpolyexp(freqs,k);
		StringBuilder ans = new StringBuilder();
		for(int i=0;i<freqs.length;i++) {
			if(freqs[i] > 0)
				ans.append(i).append(" ");
		}
		System.out.println(ans.toString().trim());
	}
	public static long[] fastpolyexp(long[] arr, int exp) {
		if(exp == 1) {
			long[] ans = new long[arr.length];
			for(int i=0;i<ans.length;i++) {
				if(arr[i] > 0)
					ans[i] = 1;
			}
			return ans;
		}
		long[] half = fastpolyexp(arr,exp/2);
		long[] ans = FFT.multiply(half, half);
		for(int i=0;i<ans.length;i++)
			if(ans[i] > 0)
				ans[i] = 1;
		if(exp % 2 == 1) {
			ans = FFT.multiply(ans, arr);
			for(int i=0;i<ans.length;i++)
				if(ans[i] > 0)
					ans[i] = 1;
		}
		return ans;
	}
	// SET maxk appropriately!!! ~log(maxn) //%
	static class FFT {
	    static final int maxk = 21, maxn = (1 << maxk) + 1;
	    // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
	    //#
	    static double[] wR = new double[maxn],
	            wI = new double[maxn],
	            rR = new double[maxn],
	            rI = new double[maxn],
	            aR  = new double[maxn],
	            aI  = new double[maxn]; //$
	    static int n, k, lastk = -1, dp[] = new int[maxn];

	    static void fft(boolean inv) {
	        if (lastk != k) {
	            lastk = k;  dp[0] = 0;
	            for (int i = 1, g = -1; i < n; i++) {
	                if ((i & (i - 1)) == 0) g++;
	                dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
	            }
	            wR[1] = 1;
	            wI[1] = 0;
	            for (int t = 0; t < k - 1; t++) {
	                double a = Math.PI / n * (1 << (k - 1 - t));
	                double curR = Math.cos(a), curI = Math.sin(a);
	                int p2 = (1 << t), p3 = p2 * 2;
	                for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
	                    wR[k] = wR[j];
	                    wI[k] = wI[j];
	                    wR[k + 1] = wR[j] * curR - wI[j] * curI;
	                    wI[k + 1] = wR[j] * curI + wI[j] * curR;
	                }
	            }
	        }
	        for (int i = 0; i < n; i++) {
	            int d = dp[i];
	            if (i < d) {
	                double tmp = aR[i];
	                aR[i] = aR[d];
	                aR[d] = tmp;
	                tmp = aI[i];
	                aI[i] = aI[d];
	                aI[d] = tmp;
	            }
	        }
	        if (inv) for (int i = 0; i < n; i++) aI[i] = -aI[i];
	        for (int len = 1; len < n; len <<= 1) {
	            for (int i = 0; i < n; i += len) {
	                int wit = len;
	                for (int it = 0, j = i + len; it < len; it++, i++, j++) {
	                    double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
	                    double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
	                    wit++;
	                    aR[j] = aR[i] - tmpR;
	                    aI[j] = aI[i] - tmpI;
	                    aR[i] += tmpR;
	                    aI[i] += tmpI;
	                }
	            }
	        }
	    }

	    static long[] multiply(long[] a, long[] b) {
	        int na = a.length, nb = b.length;
	        for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {}
	        for (int i = 0; i < n; ++i) {
	            aR[i] = i < na ? a[i] : 0;
	            aI[i] = i < nb ? b[i] : 0;
	        }
	        fft(false);
	        aR[n] = aR[0];
	        aI[n] = aI[0];
	        double q = -1.0 / n / 4.0;
	        for (int i = 0; i <= n - i; ++i) {
	            double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
	            double tmpI = aR[i] * aI[i] * 2;
	            tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
	            tmpI -= aR[n - i] * aI[n - i] * -2;
	            aR[i] = -tmpI * q;
	            aI[i] = tmpR * q;
	            aR[n - i] = aR[i];
	            aI[n - i] = -aI[i];
	        }
	        fft(true);
	        long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
	        for (int i = 0; i < n; i++) ans[i] = Math.round(aR[i]);
	        return ans;
	    }
	    static void fft2(double[][] real, double[][] imag, boolean inv) {
	        for (k = 0, n = 1; n < real[0].length; n <<= 1, k++) {}
	        for (int i = 0; i < real.length; i++) {
	            for (int j = 0; j < real[i].length; j++) {
	                aR[j] = real[i][j];
	                aI[j] = imag[i][j];
	            }
	            fft(inv);
	            for (int j = 0; j < real[i].length; j++) {
	                real[i][j] = aR[j];
	                imag[i][j] = aI[j];
	            }
	        }
	        for (k = 0, n = 1; n < real.length; n <<= 1, k++) {}
	        for (int j = 0; j < real[0].length; j++) {
	            for (int i = 0; i < real.length; i++) {
	                aR[i] = real[i][j];
	                aI[i] = imag[i][j];
	            }
	            fft(inv);
	            for (int i = 0; i < real.length; i++) {
	                real[i][j] = aR[i];
	                imag[i][j] = aI[i];
	            }
	        }
	    }
	    static long[][] multiply2(long[][] a, long[][] b) {  
	        int n1 = Integer.highestOneBit(
	                Math.max(a.length, b.length) - 1) << 2;
	        int n2 = Integer.highestOneBit(
	                Math.max(a[0].length, b[0].length) - 1) << 2;
	        n1 = Math.max(n1, 1);  n2 = Math.max(n2, 1);

	        double[][] ar = new double[n1][n2];
	        double[][] ai = new double[n1][n2];
	        double[][] br = new double[n1][n2];
	        double[][] bi = new double[n1][n2];
	        for (int i = 0; i < a.length; i++)
	            for(int j = 0; j < a[i].length; j++) ar[i][j] = a[i][j];
	        for (int i = 0; i < b.length; i++)
	            for(int j = 0; j < b[i].length; j++) br[i][j] = b[i][j];

	        fft2(ar, ai, false); fft2(br, bi, false);
	        for (int i = 0; i < n1; i++) {
	            for(int j = 0; j < n2; j++) {
	                double r1 = ar[i][j], r2 = br[i][j];
	                double i1 = ai[i][j], i2 = bi[i][j];
	                double real = r1 * r2 - i1 * i2;
	                ai[i][j] = i1 * r2+ i2*r1;
	                ar[i][j] = real;
	            }
	        }
	        fft2(ar,ai,true);  long[][] result = new long[n1][n2];
	        for (int i = 0; i < n1; i++)
	            for(int j = 0; j < n2; j++)
	                result[i][j] = Math.round(ar[i][j]);
	        return result;
	    }
	}
}