Suppose you have a sequence of k integers A = [a_1, a_2, ... , a_k] where each a_i ≥ 2. A sequence of prime integers P = [p_1, p_2, ..., p_k] is called suitable for the sequence A if a_1 is divisible by p_1, a_2 is divisible by p_2 and so on. 

A sequence of prime integers P is called friendly if there are no unique integers in this sequence. 

A sequence A is called ideal, if each sequence P that is suitable for A is friendly as well (i. e. there is no sequence P that is suitable for A, but not friendly). For example, the sequence [2, 4, 16] is ideal, while the sequence [2, 4, 6] is not ideal (there exists a sequence P = [2, 2, 3] which is suitable for A, but not friendly).

You are given n different integers x_1, x_2, ..., x_n. You have to choose exactly k of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 1000). 

The second line contains n pairwise distinct integers x_1, x_2, ..., x_n (2 ≤ x_i ≤ 10^{18}).

Output

If it is impossible to choose exactly k integers from x_1, x_2, ..., x_n in such a way that the chosen integers form an ideal sequence, print 0.

Otherwise, print k pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

Examples

Input

3 3
2 4 6


Output

0


Input

3 3
2 4 16


Output

2 4 16 


Input

4 3
2 4 6 16


Output

2 4 16

Difficulty: VERY_HARD
Tags: Number theory

Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from math import gcd

def t_prime(n):
	if n == 1:
		return False
	for p in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
		if p < n and pow(p, n - 1, n) != 1:
			return False
	return True
primes = [i for i in range(2, 10 ** 5) if t_prime(i)]
pset = set(primes)
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
if k == 1:
	print(0)
	exit()
for i in range(n):
	for j in range(i):
		(u, v) = (l[i], l[j])
		poss = gcd(u, v)
		poss2 = max(u, v) // poss
		smol = min(poss, poss2)
		if t_prime(smol) and smol not in pset:
			primes.append(smol)
			pset.add(smol)
powers = set()
count = 0
outLs = []
pgood = []
for p in primes:
	curr = []
	fp = [v for v in l if v % p == 0]
	for v in fp:
		v2 = v
		while v2 % p == 0:
			v2 //= p
		if v2 == 1:
			curr.append(v)
			powers.add(v)
	if len(curr) > 1:
		count += len(curr)
		outLs.append(curr)
		pgood.append(p)
order = [(len(lis), lis) for lis in outLs]
order.sort(key=lambda x: x[0])
if len(order) == 0:
	print(0)
	exit()
if order[-1][0] == 2 and k % 2 and (count > k):
	extra = -1
	need = -1
	last = []
	for v in l:
		if v in powers:
			continue
		v2 = v
		primesn = []
		for p in pgood:
			add = 1
			while v2 % p == 0:
				v2 //= p
				if add:
					primesn.append(p)
				add = 0
		if v2 == 1 and (need == -1 or need > len(primesn)):
			extra = v
			last = primesn
			need = len(last)
			assert need >= 2
	if need == -1 or 2 * need + 1 > k:
		print(0)
		exit()
	other = []
	out = [extra]
	for (a, b) in outLs:
		works = False
		for p in last:
			if a % p == 0:
				works = True
				break
		if works:
			out.append(a)
			out.append(b)
		else:
			other.append(a)
			other.append(b)
	assert len(out) == 2 * need + 1
	assert (k - 2 * need - 1) % 2 == 0
	ret = out + other[:k - 2 * need - 1]
	assert len(ret) == k
	print(' '.join(map(str, ret)))
	exit()
out = []
need = k
for i in range(len(order)):
	assert need != 1
	lis = order[i][1]
	if len(lis) < need - 1 or len(lis) == need or (len(lis) == need - 1 and i == len(order) - 1):
		out += lis
		need -= len(lis)
	elif len(lis) == need - 1:
		if len(lis) > 2:
			out += lis[:-1]
			need -= len(lis) - 1
			assert need == 2
	else:
		out += lis[:need]
		need = 0
assert need + len(out) == k
assert need >= 0
assert need == 0 or len(out) == count
for v in l:
	if need == 0:
		break
	if v in powers:
		continue
	v2 = v
	for p in pgood:
		while v2 % p == 0:
			v2 //= p
	if v2 == 1:
		out.append(v)
		need -= 1
if need == 0:
	print(' '.join(map(str, out)))
	exit()
else:
	print(0)