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.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

/**
 * http://codeforces.com/problemset/problem/632/E
 * solution: 9 11 13 15 17 19 21 25 27 33
 */
public class ThiefInAShop {

	/**
	 * determines if it is used as an online submission or test.
	 */
	final static boolean ONLINE_SUBMISSION = System.getProperty("ONLINE_JUDGE") != null;

	static class Run implements Runnable {

		/**
		 * determines if output should be written to a file or to console when
		 * testing locally.
		 */
		final static boolean OUTPUT_TO_FILE = false;

		// Problem-specific: this is all the fun. Solution from cellist
		@Override
		public void run() {

			int n = nextInt(), k = nextInt();
			int[] a = nextArr(n);

			a = unique(a);
			Arrays.sort(a);
			n = a.length;

			/**
			 * The idea is to turn the smallest element to 0 (a[0] = 0). If one number equals to zero, the problem can
			 * be changed to require less than or equal to k numbers in the sum instead of exactly k numbers in the sum.
			 * This allows us to use dynamics where we store for each sum (between 0 and max) the minimum amount of
			 * numbers to get it. Info stored in
			 * 
			 * dp[x] = least number of elements required to form sum x.
			 */
			int min = a[0];
			for (int i = 0; i < n; ++i) {
				a[i] -= min; // modifying the problem so a[0] = 0
			}

			int max = k * a[n - 1]; // max for modified problem
			int[] dp = new int[max + 1];
			Arrays.fill(dp, 1, max + 1, k + 1); // initially it requires more than k (k+1 is sufficient for this
												// purpose) to get all sums, except 0
			for (int i = 1; i < n; ++i) {
				for (int j = a[i]; j <= max; ++j) { // loop through the sums
					dp[j] = Math.min(dp[j - a[i]] + 1, dp[j]); // to get j it requires it requires one more term than to
																// get j - a[i] or what it requires to get j (initially
																// more than k).
				}
			}

			for (int i = 0; i <= max; ++i) {
				if (dp[i] <= k) { // can k or less elements be used to get the sum i?
					int realSum = i + k * min; // adjust for the modified problem earlier.
					print(realSum + " ");
				}
			}

		}

		public static int[] unique(int[] arr) {
			Set<Integer> set = new HashSet<>(arr.length);
			for (int ai : arr) {
				set.add(ai);
			}
			int[] rs = new int[set.size()];
			int idx = 0;
			for (int si : set) {
				rs[idx++] = si;
			}
			return rs;
		}

		// ==============================================================
		// ======== Everything below is used across all problems ========
		// ==============================================================
		final String className = getClass().getEnclosingClass().getSimpleName();
		final String inputFilename = "io/input-" + className + ".txt";
		final String outputFilename = "io/output-" + className + ".txt";
		BufferedReader in;
		PrintWriter out;
		StringTokenizer strTok;

		Run() {
			if (ONLINE_SUBMISSION) {
				initConsoleIO();
			}
			else {
				initFileIO();
			}
		}

		/**
		 * read input from console and write output to console.
		 */
		void initConsoleIO() {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
		}

		/**
		 * read input from {@value #inputFilename} and write output to console
		 * or
		 * to {@value #outputFilename} depending on {@link #OUTPUT_TO_FILE}.
		 */
		void initFileIO() {
			try {
				in = new BufferedReader(new FileReader(inputFilename));
				if (OUTPUT_TO_FILE) {
					out = new PrintWriter(new FileWriter(outputFilename));
				}
				else {
					out = new PrintWriter(new OutputStreamWriter(System.out));
				}
			}
			catch (FileNotFoundException e) {
				e.printStackTrace();
			}
			catch (IOException e) {
				e.printStackTrace();
			}
		}

		/**
		 * Close BufferedReader and PrintWriter.
		 */
		void close() {
			try {
				in.close();
				out.close();
			}
			catch (IOException e) {
				e.printStackTrace();
			}
		}

		int nextInt() {
			return Integer.parseInt(nextToken());
		}

		double nextDouble() {
			return Double.parseDouble(nextToken());
		}

		float nextFloat() {
			return Float.parseFloat(nextToken());
		}

		long nextLong() {
			return Long.parseLong(nextToken());
		}

		String nextLine() {
			try {
				return in.readLine();
			}
			catch (IOException e) {
				return "__NULL";
			}
		}

		public int[] nextArr(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; ++i) {
				a[i] = nextInt();
			}
			return a;
		}

		// boolean hasMoreTokens() {
		// return (strTok == null) || (strTok.hasMoreTokens());
		// }

		String nextToken() {
			while (strTok == null || !strTok.hasMoreTokens()) {
				String line;
				try {
					line = in.readLine();
					strTok = new StringTokenizer(line);
				}
				catch (IOException e) {
					e.printStackTrace();
				}
			}

			return strTok.nextToken();
		}

		/**
		 * output to console.
		 */
		void cout(Object o) {
			System.out.println(o);
		}

		/**
		 * writes to PrintWriter. See {@link java.io.PrintWriter#write(String)
		 * PrintWriter.write} for more details.
		 */
		void print(Object o) {
			out.write(o.toString());
		}

		/**
		 * writes to PrintWriter and add new line. See
		 * {@link java.io.PrintWriter#write(String)
		 * PrintWriter.write} for more details.
		 */
		void println(Object o) {
			out.write(o.toString() + '\n');
		}

		/**
		 * See documentation {@link java.io.PrintWriter#printf(String, Object)
		 * here}.
		 */
		void printf(String format, Object... args) {
			out.printf(format, args);
		}

		/**
		 * See documentation
		 * {@link java.text.MessageFormat#format(String, Object) here}.
		 */
		String sprintf(String format, Object... args) {
			return MessageFormat.format(format, args);
		}
	}

	public static void main(String[] args) throws IOException {
		Run run = new Run();
		Thread thread = new Thread(run);
		if (!ONLINE_SUBMISSION) {
			long start = System.currentTimeMillis();
			thread.run();
			System.out.println("Time elapsed: " + ((System.currentTimeMillis() - start) / 1000.0) + " sec\n");
		}
		else {
			thread.run();
		}
		run.close();
	}
}