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
///package Assignment6;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;

public class CodeForces_E_632 {

	static long[] numbers;
	static int max,k;
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		numbers = new long[1001];
		// i will create k plynomials and multiply them together
		st = new StringTokenizer(bf.readLine());
		long[] arr = new long[n];
		
		for (int i = 0; i < n; i++) {
			int nn = Integer.parseInt(st.nextToken());
			if(max <= nn)
				max=nn;
			numbers[nn] = 1L;
		}
		long[] result = Pow(numbers, k);
		print(result);

	}
	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 void print(long[] arr) {
		PrintWriter pw = new PrintWriter(System.out);
		max=(int)Math.pow(max, k);
		max+=max+k;
		max=Math.min(max, arr.length);
		int var=-1;
		for (int i = 0; i < arr.length; i++) {
				if (arr[i] > 0){
					pw.print(i + " ");
//					if(var ==-1){
//						var=i;
//						
//					}
//					else{
//						pw.print(var + " ");
//						var=i;
//					}
				}
				
			
		}
		pw.flush();
		pw.close();
	}

	static long[] Pow(long[] p, long e) {// multiple the polynomial feh nafsha k									// times
		long[] result = new long[1];// di ihtmal tkon ghalt
		result[0]=1;

		while (e > 0) {
			//yahsn yhsal overflow low tle hashilha  
			for (int i = 0; i < result.length; i++) {
				if(result[i] > 1)
					result[i]=1;
			}
			for (int i = 0; i < p.length; i++) {
				if(p[i] > 1)
					p[i]=1;
			}
			if ((e & 1) != 0) {
				result = multiply(result, p);
			}
			e >>= 1;

			p = multiply(p, p);
		}
		return result;
	}



}
