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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class FFT {
	static void fft(double[] ar, double[] ai, boolean inverse) {
		int n = ar.length;

		for (int i = 1, j = 0; i < n; i++) {

			int bit = n >> 1;
			for (; j >= bit; bit >>= 1)
				j -= bit;
			j += bit;

			if (i < j) {
				double tmp = ar[i];
				ar[i] = ar[j];
				ar[j] = tmp;

				tmp = ai[i];
				ai[i] = ai[j];
				ai[j] = tmp;
			}
		}

		for (int len = 2; len <= n; len <<= 1) {
			double angle = 2 * Math.PI / len * (inverse ? -1 : 1);

			int len2 = len >> 1;

			double wnr = Math.cos(angle);
			double wni = Math.sin(angle);

			for (int i = 0; i < n; i += len) {

				double wr = 1;
				double wi = 0;

				for (int j = 0; j < len2; j++) {
					double ur = ar[i + j];
					double ui = ai[i + j];

					double vr = realMult(ar[i + j + len2], ai[i + j + len2], wr, wi);
					double vi = imagMult(ar[i + j + len2], ai[i + j + len2], wr, wi);

					ar[i + j] = ur + vr;
					ai[i + j] = ui + vi;

					ar[i + j + len / 2] = ur - vr;
					ai[i + j + len / 2] = ui - vi;

					double twr = wr;
					double twi = wi;

					wr = realMult(twr, twi, wnr, wni);
					wi = imagMult(twr, twi, wnr, wni);
				}
			}

		}

		if (inverse)
			for (int i = 0; i < n; i++) {
				ar[i] /= n;
				ai[i] /= n;
			}
	}

	static double realMult(double ar, double ai, double br, double bi) {
		return ar * br - ai * bi;
	}

	static double imagMult(double ar, double ai, double br, double bi) {
		return ar * bi + ai * br;
	}

	static long[] multiply(long[] a, long[] b) {
		
		// enter the polynomials in the parameters as is.

		int N = 1;
		while (N < Math.max(a.length, b.length))
			N <<= 1;

		N <<= 1;

		double ar[] = new double[N];
		double ai[] = new double[N];

		double br[] = new double[N];
		double bi[] = new double[N];

		for (int i = 0; i < a.length; i++) {
			ar[i] = a[i];
		}
		for (int i = 0; i < b.length; i++) {
			br[i] = b[i];
		}

		fft(ar, ai, false);

		if (a == b) {
			for (int i = 0; i < N; i++) {
				double real = ar[i];
				double imag = ai[i];
				ar[i] = realMult(real, imag, real, imag);
				ai[i] = imagMult(real, imag, real, imag);
			}
		} else {
			fft(br, bi, false);
			for (int i = 0; i < N; i++) {
				double real = ar[i];
				double imag = ai[i];
				ar[i] = real * br[i] - imag * bi[i];
				ai[i] = real * bi[i] + imag * br[i];
			}
		}

		fft(ar, ai, true);

		long[] res = new long[N];

		for (int i = 0; i < N; i++) {
			res[i] = (long) (ar[i] + 0.5);
		}

		return res;
	}
	static int getMax (StringTokenizer arr)  {
		int max =-1;
		while(arr.hasMoreTokens()) {
			int comp = Integer.parseInt(arr.nextToken());
			if (max < comp)
				max = comp;
		}
//		for (int i = 0; i < arr.length; i++) {
//			int comp = Integer.parseInt(arr[i]);
//			if (max < comp)
//				max = comp;
//		}
		return max;
	}
	static long[] pow (long[] a, long b) {
		if (b == 1) return a;
		if (b == 0) return new long[1];
		if (b%2 == 1){
			long[] y = pow(a,b-1);
			return multiply(a, y);
		}
		long[] x = pow(a,(long)b/2);
		return multiply(x, x);
	}
	static long[] powIterative (long[] a, long k) {
		long b[] = { 1 };

		while (k > 0) {
			
			for(int i=0; i<a.length; i++)
				a[i] = Math.min(a[i], 1);
			
			for(int i=0; i<b.length; i++)
				b[i] = Math.min(b[i], 1);
			
			if ((k & 1) > 0) {
				b = multiply(a, b);
			}
			a = multiply(a, a);
			k >>= 1;
		}
		return b;
		}

	public static void main(String [] args) throws NumberFormatException, IOException{

		PrintWriter pw = new PrintWriter(System.out);
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer seq = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(seq.nextToken());
		int k =  Integer.parseInt(seq.nextToken());
		String as = bf.readLine();
		StringTokenizer costs = new StringTokenizer(as);
		//int max = getMax(new StringTokenizer(as));
		long [] arr = new long [1000+1];
		for (int i = 0; i < n; i++) {
			arr[Integer.parseInt(costs.nextToken())] = 1;
		}
		long [] result = powIterative(arr, k); 
		
//		for (int i = 0; i < k-1; i++) {
//			result = multiply(arr,result);
//		}
		//ArrayList <Integer> finalResult = new ArrayList<Integer>();
		for (int i = 0; i < result.length;i++) {
			if (result[i] > 0)
				//finalResult.add(i);
				pw.print(i + " ");
		}
		/*
		Object[] resultArr = new Integer[finalResult.size()];
		resultArr = finalResult.toArray();
		Arrays.sort(resultArr);
		for (int j = 0; j < resultArr.length; j++) {
			pw.print(resultArr[j]);
			if (j < resultArr.length - 1) {
				pw.print(" ");
			}
		}
		*/
		pw.flush();
		pw.close();
	/*
		long [] a = {0,2,0,0};
		long [] b = {0,1,0,0};
		//ntt(b, false);
		long [] res = multiply(a, b);
		for(int i = 0; i < res.length; i++) {
			System.out.print(res[i] + ",");
		}
*/
	}

}