At the time when Pythagoreanism was prevalent, people were also focused on different ways to factorize a number. In one class, Pythagoras asked his disciples to solve one such problem, Reverse Factorization. They were given a set of integer, $A=\{a_1,a_2,\cdots,a_K\}$, and an integer $N$. They need to find the a way to reach $N$, starting from $\mbox{1}$, and at each step multiplying current value by any element of $\mbox{A}$. But soon they realised that there may exist more than one way to reach $N$. So they decided to find a way in which number of states are least. All of sudden they started on this new problem. People solved it and then started shouting their answer. CRAP!!!. There still exists multiple answers. So finally after much consideration, they settled on the lexicographically smallest series among those solutions which contains the least number of states.

For example, if $N=12$ and $A=2,3,4$ then following ways exists  

(a) 1  ->  2  ->  4  ->  12
       x2     x2     x3

(b) 1  ->  4  ->  12
       x4     x3

(c) 1  ->  3  ->  12
       x3     x4

Here (a) is not the minimal state, as it has $\begin{array}{c}4\end{array}$ states in total. While (b) and (c) are contenders for answer, both having 3 states, (c) is lexicographically smaller than (b) so it is the answer. In this case you have to print 1 3 12. If there exists no way to reach $N$ print -1.   

Input Format

Input contains two lines where first line contains two space separated integer, $N$ and $\mbox{K}$, representing the final value to reach and the size of set $\mbox{A}$, respectively. Next line contains K space integers representing the set $A=\{a_1,a_2,\cdots,a_K\}$.

Constraints

$1\leq N\leq10^9$  
$1\leq K\leq20$  
$2\leq a_i\leq20$, where $i\in[1,K]$  
$a_i\neq a_j$, where $1\leq i,j\leq K$ AND $i\neq j$  

Note:  

Lexicographical order: If $list1=[p_1,p_2,\cdots,p_m]$ and $list2=[q_1,q_2,\cdots,q_n]$ are two ordered lists, then $list1$ is lexicographically smaller than $list2$ if any one of the following condition satisfies.  

$p_i=q_i,\forall i\in[1,m]$ AND $m<n$.  
$p_i=q_i,\forall i\in[1,k]$ AND $k<min(m,n)$ AND $p_{k+1}<q_{k+1}$.  

You need to find the lexigraphically smallest series among those solutions which contains the least number of states.  

Output Format

Print the steps to reach $N$ if it exists. Otherwise print -1.

Sample Input 0
12 3
2 3 4

Sample Output 0
1 3 12

Explanation 0

This is the same case which is explaned above.  

Sample Input 1
15 5
2 10 6 9 11

Sample Output 1
-1

Explanation 1

Here no way exists so that we can reach $15$ starting from $\mbox{1}$.  

Sample Input 2
72 9
2 4 6 9 3 7 16 10 5

Sample Output 2
1 2 8 72

Explanation 2

There are multiple ways to reach 72 using these 8 numbers. Out of which following 6 ways consists of minimal states (4).  

States          =>  Multiplication operation
 1   9  18  72  =>      (x9, x2, x4)
 1   4  36  72  =>      (x4, x9, x2)
 1   2   8  72  =>      (x2, x4, x9)
 1   2  18  72  =>      (x2, x9, x4)
 1   4   8  72  =>      (x4, x2, x9)
 1   9  36  72  =>      (x9, x4, x2)

As series 1 2 8 72 is lexicographically smallest, it is the answer.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
def getResult(n, a):
	if n is 1:
		return []
	for x in a:
		if n % x is 0:
			break
	else:
		return False
	for x in a:
		if n % x is 0:
			result = getResult(int(n / x), a)
			if result is not False:
				result.append(x)
				return result
	return False
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
result = getResult(n, a)
if result is False:
	print(-1)
else:
	current = 1
	print(current, end=' ')
	for x in result:
		current *= x
		print(current, end=' ')


def m(A, B):
	return min(A, B)

def solve(A, n):
	if n in D:
		return D[n]
	if n == 1:
		return (True, [])
	if n < 1:
		return (False, [])
	S = []
	s = False
	for a in A:
		if n % a != 0:
			continue
		t = solve(A, n // a)
		if t[0]:
			if s:
				S = [a] + m(S, t[1])
				s = True
			else:
				S = [a] + t[1]
	if not S:
		D[n] = (False, [])
		return (False, [])
	D[n] = (True, S)
	return (True, S)
(N, K) = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
A.sort()
D = {}
A = solve(A, N)
i = 1
if A[0]:
	print('1', end=' ')
	for a in sorted(A[1]):
		i *= a
		print(i, end=' ')
	print('')
else:
	print('-1')


(N, K) = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
a = [x for x in a if N % x == 0]
factors = []

def find(n, index):
	if n == 1:
		return True
	if index == len(a):
		return False
	x = a[index]
	(div, mod) = divmod(n, x)
	if mod == 0:
		factors.append(x)
		if find(div, index):
			return True
		factors.pop()
	return find(n, index + 1)
if find(N, 0):
	factors.reverse()
	answers = [1]
	for factor in factors:
		answers.append(answers[-1] * factor)
	print(*answers)
else:
	print(-1)


def factor(n, A, Answer):
	if n == 1:
		return Answer
	num = -1
	for a in A:
		if n % a == 0:
			num = n // a
			Answer.append(str(num))
			break
	if num == -1:
		return ['-1']
	return factor(num, A, Answer)
(N, k) = [int(x) for x in input().split(' ')]
A = list(reversed(sorted([int(x) for x in input().split(' ')])))
Answer = list(reversed(factor(N, A, [str(N)])))
print(' '.join(Answer))


def factRec(num, flag):
	if len(A) == 0:
		if flag == 0:
			return -1
		else:
			return 0
	if num % A[0] == 0:
		if flag == 0:
			factList.append(num)
			flag = 1
		pivot = num / A[0]
		factList.append(int(pivot))
		return factRec(pivot, flag)
	else:
		pivot = num
		del A[0]
		return factRec(pivot, flag)
(n, k) = input().split()
(n, k) = (int(n), int(k))
A = list(map(int, input().strip().split(' ')))
factList = []
flag = 0
A.sort(reverse=True)
x = factRec(n, flag)
if len(factList) == 0 or factList[-1] != 1:
	print(-1)
else:
	factList.reverse()
	print(*factList)


def main():
	(n, k) = [int(tmp) for tmp in input().strip().split(' ')]
	a = list(sorted((int(tmp) for tmp in input().strip().split(' '))))
	stack = []
	stack.append((0, [], n))
	ans = None
	while stack:
		(idx, acc, cur) = stack.pop()
		if cur == 1:
			if ans is None or len(acc) < len(ans) or (len(acc) == len(ans) and acc < ans):
				ans = acc
		for i in range(idx, k):
			acc2 = acc
			cur2 = cur
			while cur2 % a[i] == 0:
				acc2 = acc2[:]
				acc2.append(a[i])
				cur2 //= a[i]
				stack.append((i + 1, acc2, cur2))
	if ans is None:
		print(-1)
		return
	acc = 1
	for fac in ans:
		print(acc, end=' ')
		acc *= fac
	print(acc)
main()


from copy import deepcopy
from functools import reduce

def sorted_factor(list_factors1, target, counter, holder):
	if len(holder) > 1 and counter == target:
		print(1, end=' ')
		counter = 1
		for Y in sorted(holder):
			print(counter * Y, end=' ')
			counter *= Y
		return True
	new_holder = deepcopy(holder)
	new_counter = deepcopy(counter)
	new_factors = deepcopy(list_factors1)
	for A in reversed(list_factors1):
		_X = target / (counter * A)
		for B in list_factors1:
			if _X == 1 or _X % B == 0:
				new_holder.append(A)
				new_counter = counter * A
				if sorted_factor(list_factors1, target, new_counter, new_holder):
					return True
				return False
	print(-1)
	return False
first_row = input().split(' ')
target = int(first_row[0])
second_row = input().split(' ')
list_factors = [int(Q) for Q in second_row]
list_factors = sorted([X for X in list_factors if target % X == 0])
if len(list_factors) == 0:
	print(-1)
else:
	sorted_factor(list_factors, target, 1, list())


from collections import deque
(N, K) = map(int, input().strip().split(' '))
factors = map(int, input().strip().split(' '))
factors = sorted(factors)

def DFS(N, factors):
	stack = list([(N, [N])])
	while stack:
		(target, factorization) = stack.pop()
		for factor in factors:
			if target == factor:
				return factorization + [1]
			elif target % factor == 0 and target // factor > 1:
				stack.append((target // factor, factorization + [target // factor]))
	return (-1,)
print(' '.join(map(str, DFS(N, factors)[::-1])))


[N, K] = list(map(int, input().strip().split(' ')))
A = list(map(int, input().strip().split(' ')))
A = sorted(A)

def find(N, A):
	L = []

	def mod(N, L):
		for i in range(1, len(A) + 1):
			if N % A[-i] == 0 and A[-i] > 1:
				L += [N // A[-i]]
				N = N // A[-i]
				break
		else:
			return 0
		mod(N, L)
	mod(N, L)
	L.reverse()
	if L == []:
		return L
	elif L[0] != 1:
		return []
	else:
		return L
L = find(N, A)
if L == []:
	print(-1)
else:
	for i in range(len(L)):
		print(L[i], end=' ')
	print(N)


from collections import deque

def get_reverse_factorization(n, factors):
	frontier = deque([(1, [])])
	visited = set([])
	while frontier:
		(current, path) = frontier.pop()
		if current == n:
			return reversed(path)
		for f in factors:
			nbr = current * f
			if nbr <= n and nbr not in visited:
				frontier.appendleft((nbr, path + [f]))
				visited.add(nbr)
(n, _) = map(int, input().split())
factors = [int(i) for i in input().split()]
factors.sort(reverse=True)
factorization = get_reverse_factorization(n, factors)
if factorization is None:
	print(-1)
else:
	current = 1
	for factor in factorization:
		print(current, end=' ')
		current *= factor
	print(current)


def f(n, m):
	if n in m:
		return m[n]
	not_divisible = True
	for e in a:
		if e == n:
			m[n] = [e]
			return m[n]
		if n % e == 0:
			not_divisible = False
	if not_divisible:
		m[n] = None
		return m[n]
	results = []
	for e in a:
		if n % e == 0:
			result = f(n // e, m)
			if result:
				results.append([e] + result)
	if results == []:
		m[n] = None
		return m[n]
	results.sort(key=lambda x: (len(x), x[0]))
	m[n] = results[0]
	return m[n]
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
result = f(n, {})
if result:
	p = 1
	factorials = [1]
	for x in result:
		p *= x
		factorials.append(p)
	print(' '.join([str(x) for x in factorials]))
else:
	print(-1)


import itertools as it
import operator
memos = {}

def is_better(a, b):
	if a:
		if b:
			la = len(a)
			lb = len(b)
			return la < lb or (la == lb and a < b)
		else:
			return True

def fn(m):
	shortest = memos.get(m)
	if shortest is None:
		g = ([v, m // v] for v in a if m >= v and m % v == 0)
		for (v, q) in g:
			if q == 1:
				shortest = (v,)
				break
			elif q:
				t = fn(q)
				if t:
					t = (v,) + t
					if is_better(t, shortest):
						shortest = t
		memos[m] = shortest or False
	return shortest
(n, _) = map(int, input().split())
g = map(int, input().split())
g = (v for v in g if 1 < v < n and n % v == 0)
a = sorted(g, reverse=True)
r = fn(n)
if r:
	print(1, *it.accumulate(r, operator.mul))
else:
	print(-1)


(n, k) = input().strip().split()
(n, k) = [int(n), int(k)]
a = [int(a_temp) for a_temp in input().strip().split()]
a.sort(reverse=True)
arr = []
for i in a:
	if i == 1:
		break
	while n / i == n // i:
		n = n // i
		arr.append(i)
if n == 1:
	arr.reverse()
	num = 1
	answers = [1]
	for i in arr:
		answers.append(i * answers[-1])
	print(*answers)
else:
	print('-1')


import collections
(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
active = collections.deque()
active.append((1, 0))
prev = {1: 0}
while active:
	(prod, i) = active.popleft()
	if prod == n:
		out = []
		while prod:
			out.append(str(prod))
			prod = prev[prod]
		out.reverse()
		print(' '.join(out))
		break
	while i < k:
		newprod = prod * a[i]
		if newprod > n:
			break
		if newprod not in prev:
			prev[newprod] = prod
			active.append((newprod, i))
		i += 1
else:
	print(-1)


def kfact(N, ar):
	if N == 1:
		return [[1]]
	cases = []
	for (k, a) in enumerate(ar):
		if N % a == 0:
			cases += [c + [a * c[-1]] for c in kfact(N // a, ar[k:])]
	return cases

def parse(cases):
	if len(cases) == 0:
		return -1
	mlen = min((len(x) for x in cases))
	return ' '.join((str(x) for x in min((c for c in cases if len(c) == mlen))))
((N, K), ar) = ([int(x) for x in input().split()], sorted([int(x) for x in input().split()], reverse=True))
print(parse(kfact(N, ar)))


from collections import deque

def solve(N, K, F):
	q = deque([1])
	p = {1: -1}
	while q:
		num = q.pop()
		for f in F:
			nf = num * f
			if nf > N:
				break
			nx = p.get(nf, None)
			if nx != None:
				continue
			p[nf] = num
			if nf == N:
				path = [nf]
				while True:
					nf = p[nf]
					if nf == -1:
						break
					path.append(nf)
				return path
			q.appendleft(nf)
	return None
(N, K) = map(int, input().strip().split())
F = sorted(map(int, input().strip().split()))
res = solve(N, K, F)
if res:
	print(' '.join((str(c) for c in res[::-1])))
else:
	print(-1)


from itertools import accumulate
from operator import mul
import heapq
(n, _) = (int(x) for x in input().split())
nums = (int(x) for x in input().split())
heap = [x for x in nums if n % x == 0]
heapq.heapify(heap)
dp = {x: [x] for x in heap}
processed = []
while heap and (not processed or n / heap[0] > processed[0]):
	x = heapq.heappop(heap)
	for y in processed:
		z = x * y
		if z > n:
			break
		if n % z:
			continue
		current_path = dp.get(z, [])
		if current_path and len(dp[x]) + len(dp[y]) > len(current_path):
			continue
		path = sorted(dp[x] + dp[y])
		if not current_path or path < current_path:
			dp[z] = path
		if not current_path:
			heapq.heappush(heap, z)
	processed.append(x)
print(' '.join((str(x) for x in accumulate([1] + dp[n], mul))) if n in dp else -1)


def main():
	n = int(input().split(' ')[0])
	_list = [int(x) for x in input().split(' ')]
	_list.sort(reverse=True)
	divisors = []
	i = 0
	while i < len(_list) and n > 1:
		while n % _list[i] == 0:
			divisors.append(_list[i])
			n //= _list[i]
		i += 1
	if n == 1:
		divisors.sort()
		i = 1
		for x in divisors:
			print(i, end=' ')
			i *= x
		print(i)
	else:
		print('-1')
main()


(n, k) = map(int, input().split())
a = list(sorted(map(int, input().split())))
p = {1: [1]}

def f(n):
	if n not in p:
		x = [-1]
		for i in a:
			if not n % i:
				x = min(x, list(sorted([i] + f(n // i))), key=lambda i: (len(i), i) if i[0] != -1 else (100, []))
		p[n] = x
	return p[n]
y = f(n)
for i in range(1, len(y)):
	y[i] *= y[i - 1]
print(*y)


(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
l = [int(i) for i in input().strip().split(' ')]
x = []
l.sort()
l.reverse()
prod = int(1)
length = len(l)
flag = int(0)
while n > 1:
	flag = int(0)
	for i in range(length):
		if n % l[i] == 0 and n > 0 and (flag == 0):
			flag = 1
			x.append(n)
			n = int(n / l[i])
			break
	if flag == 0:
		break
x.append(1)
x.reverse()
if prod < n:
	print(-1)
else:
	for i in x:
		print(i, end=' ')


n = int(input().split()[0])
S = list(map(int, input().split()))
S.sort()
S.reverse()
mults = []

def recurse(n):
	if n == 1:
		return
	for i in S:
		if n % i == 0:
			mults.append(i)
			recurse(n // i)
			break
recurse(n)
mults.sort()
prod = 1
ans = [1]
for i in mults:
	prod *= i
	ans.append(prod)
if ans[-1] == n:
	for i in ans:
		print(i, end=' ')
else:
	print(-1)


from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))

def solve(N, A):
	A.sort()
	memo = {1: None}
	queue = deque()
	queue.append(1)
	while queue:
		n = queue.popleft()
		if n == N:
			ans = [n]
			while n > 1:
				n //= memo[n]
				ans.append(n)
			return ans[::-1]
		for a in A:
			d = n * a
			if d not in memo and N % d == 0:
				memo[d] = a
				queue.append(d)
	return [-1]
print(' '.join(map(str, solve(N, A))))


from collections import deque
from operator import mul
from functools import reduce
(N, K) = input().split()
(N, K) = (int(N), int(K))
numbers = sorted([int(x) for x in input().split()])
queue = deque([[n] for n in numbers])
products_had = set()
old_len = 0
while True:
	try:
		n = queue.popleft()
	except:
		print('-1')
		break
	product = reduce(mul, n, 1)
	if len(n) > old_len:
		old_len = len(n)
		if product > N:
			print('-1')
			break
	if product in products_had:
		continue
	if product == N:
		total = 1
		print_str = '1'
		for x in n:
			total *= x
			print_str += ' ' + str(total)
		print(print_str)
		break
	if product < N:
		products_had.add(product)
		for num in numbers:
			queue.append(n + [num])


def finding(n, arr):
	result = []
	i = len(arr) - 1
	result.append(n)
	while n >= 1 and i >= 0:
		while n % arr[i] == 0:
			n = n / arr[i]
			if n == 1:
				result.insert(0, n)
				break
			result.insert(0, n)
		i = i - 1
	if result[0] != 1:
		return -1
	return result

def print_result(arr):
	string = ''
	if type(arr) == int:
		print(arr)
		return
	for i in range(len(arr)):
		string = string + str(int(arr[i])) + ' '
	print(string)
info = input().split()
n = int(info[0])
nums = int(info[1])
ori_list = [int(t) for t in input().split()]
ori_list.sort()
print_result(finding(n, ori_list))


(n, k) = input().split(' ')
(n, k) = [int(n), int(k)]
a = [int(i) for i in input().split(' ')]
a = list(reversed(sorted(a)))
ans = []
ans.append(n)
for j in a:
	while n % j == 0:
		n = n // j
		ans.append(n)
if 1 not in ans:
	print('-1')
else:
	for i in range(len(ans)):
		print(ans[len(ans) - i - 1], end=' ')


(n, k) = input().strip().split(' ')
n = int(n)
k = int(k)
ar = list(map(int, input().strip().split(' ')))
ar.sort(reverse=True)
result_list = [n]
i = 0
while i < k:
	if n % ar[i] == 0:
		result_list.append(int(n / ar[i]))
		if n / ar[i] == 1:
			break
		else:
			n = n / ar[i]
	else:
		i += 1
result_list.sort()
if result_list[0] is not 1:
	print(-1)
else:
	print(*result_list)


import sys
(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
nums = [int(temp) for temp in input().strip().split(' ')]
nums.sort(key=lambda i: -i)
res = [n]
start = 0
while n > 1:
	i = start
	while i < len(nums):
		if n % nums[i] == 0:
			n = n // nums[i]
			res.append(n)
			start = i
			break
		i += 1
	if i == len(nums):
		break
res = res[::-1]
if res[0] != 1:
	print(-1)
else:
	print(*res)


res = {}

def get_result(m, A):
	if not m in res:
		min_old = 10000000
		d_old = 0
		new_result = [-1]
		for d in A:
			if m % d == 0:
				x = get_result(m // d, A)
				if x[0] > -1 and d > d_old:
					new_result = x + [m]
					d_old = d
		res[m] = new_result
	return res[m]

def print_list(my_list):
	s = ''
	for x in my_list:
		s = s + str(x) + ' '
	print(s)
for query in [0]:
	(m, n) = input().strip().split(' ')
	(m, n) = (int(m), int(n))
	A = list(map(int, input().strip().split(' ')))
	res = {1: [1]}
	print_list(get_result(m, A))


import sys
sys.setrecursionlimit(2000)

def rec(n, a):
	if len(a) == 0:
		return 1
	for i in a:
		if n % i == 0:
			res.append(i)
			return rec(n / i, a[1:])
	return -1

def main():
	(n, k) = input().split(' ')
	sm = input().split(' ')
	a = [int(float(i)) for i in sm]
	a.sort()
	i = len(a) - 1
	while i >= 0:
		j = i
		t = int(float(n))
		res = []
		while j >= 0:
			while t % a[j] == 0:
				t /= a[j]
				res.append(a[j])
			if t == 1:
				print(int(t), end=' ')
				u = len(res) - 1
				while u >= 0:
					t *= res[u]
					print(int(t), end=' ')
					u -= 1
				return
			j -= 1
		i -= 1
	print('-1')
main()


def largest_factor(n, factors):
	for factor in reversed(factors):
		if n % factor == 0:
			return factor
	return None

def smallest_factor_sequence(n, factors):
	if n == 1:
		return [n]
	largest = largest_factor(n, factors)
	if largest is None:
		return None
	solution = smallest_factor_sequence(n // largest, factors)
	if solution is not None:
		solution.append(n)
	return solution
(n, factors_size) = input().strip().split()
n = int(n)
factors_size = int(factors_size)
factors = list(map(int, input().split()))
factors.sort()
output = smallest_factor_sequence(n, factors)
if output is not None:
	print(*output)
else:
	print(-1)


def myfunc(num, array, temp, numarray):
	i = 0
	while num >= 1 and i < len(numarray) and (len(array) == 0):
		if num % numarray[i] == 0:
			num = int(num // numarray[i])
			temp.append(num)
			s = temp[:]
			array = myfunc(num, array, s, numarray)
			temp.pop()
			num = int(num * numarray[i])
		i += 1
	if num == 1 and len(array) == 0:
		s = temp[:]
		if s not in array:
			array.append(temp)
	return array

def tostr(array):
	strs = ''
	for i in array:
		strs += str(i)
		strs += ' '
	return strs
(t, n) = input().split()
t = int(t)
n = int(n)
array = input().split()
fin = []
for i in array:
	fin.append(int(i))
fin.sort(reverse=True)
newar = []
temp = [t]
newar = myfunc(t, newar, temp, fin)
lenar = []
finar = []
if len(newar) == 0:
	print(-1)
else:
	print(tostr(newar[0][::-1]))


dp = {}

def f_compare(a, b):
	a_key = ''.join(['%02d' % d for d in a])
	b_key = ''.join(['%02d' % d for d in b])
	if a_key > b_key:
		return 1
	elif a_key < b_key:
		return -1
	else:
		return 0

def k_factorization(N, K, A, F, All):
	A_ = [N // x for x in A if N % x == 0]
	if len(A_) == 0:
		return
	if len([x for x in A_ if x != 1]) == 0:
		F.append(1)
		F.sort()
		All.append(F)
		dp[N] = F
		return
	for i in range(len(A_)):
		F_ = list(F) if F != None else [N]
		if F == None or not A_[i] in dp or f_compare(F, dp[A_[i]]) < 0:
			F_.append(A_[i])
			k_factorization(A_[i], K, A, F_, All)
		else:
			F_.extend(dp[A_[i]])
			F_.sort()
			dp[N] = F_
			All.append(F_)
(N, K) = [int(x) for x in input().strip().split(' ')]
A = [int(x) for x in input().strip().split(' ')]
A.sort(reverse=True)
All = []
k_factorization(N, K, A, None, All)
if len(All) > 0:
	min_length = len(min(All, key=lambda f: len(f)))
	All_ = [f for f in All if len(f) == min_length]
	All_ = sorted(All_, key=lambda f: ''.join(['%02d' % d for d in f]))
	print(' '.join([str(d) for d in All_[0]]))
else:
	print(-1)


(n, _) = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr, reverse=True)
ans = [n]
for i in arr:
	while n % i == 0:
		ans.insert(0, n // i)
		n //= i
	if n == 1:
		print(' '.join(map(str, ans)))
		break
else:
	print(-1)


def kfactorization(alon, x):
	alon.sort()
	alon.reverse()
	k = len(alon)
	temp = list(alon)
	for i in alon:
		if x % i != 0:
			temp.remove(i)
	alon = temp
	if x == 1:
		return '1'
	elif alon == []:
		return '-1'
	else:
		return str(int(x)) + ' ' + kfactorization(alon, x / alon[0])
goal = input()
goal = list(map(int, goal.split(' ')))[0]
a = input()
a = list(map(int, a.split(' ')))
res = kfactorization(a, goal)
res = res.split(' ')
if '-1' in res:
	print('-1')
else:
	res.reverse()
	final = ' '.join((str(e) for e in res))
	print(final)


(N, k) = map(int, input().split())
a = list(map(int, input().split()))
factors = sorted([f for f in a if N % f == 0], key=lambda x: -x)
res = 1
i = 0
seq = []
q = N
while res < N and i < len(factors):
	if q % factors[i] != 0:
		i += 1
		continue
	res = res * factors[i]
	seq.append(factors[i])
	q = q / factors[i]
	if q >= factors[i] and q % factors[i] == 0:
		while q >= factors[i] and q % factors[i] == 0:
			res = res * factors[i]
			q = q / factors[i]
			seq.append(factors[i])
	i += 1
if res != N:
	print(-1)
else:
	resSeq = [1]
	res = 1
	for e in sorted(seq):
		res *= e
		resSeq.append(res)
	print(*resSeq, sep=' ')


def factorize(n):
	result = []
	for number in a:
		if n % number == 0:
			result.append(number)
	return sorted(result)
(n, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
factors = factorize(n)
minimum_req = 0
number = n
actual_factors = []
for i in range(len(factors)):
	while number % factors[-i - 1] == 0:
		number = number / factors[-i - 1]
		actual_factors.insert(0, factors[-i - 1])
		minimum_req += 1
product = 1
result = [product]
for i in range(len(actual_factors)):
	product *= actual_factors[i]
	result.append(product)
print(*result) if len(result) > 1 and number == 1 else print(-1)


(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
l = len(nums)
lis = []
i = l - 1
while n != 1 or i != -1:
	if i == -1:
		break
	if n % nums[i] == 0:
		n = n / nums[i]
		lis.append(nums[i])
		i = l - 1
	else:
		i = i - 1
if n > 1:
	print(-1)
else:
	l = len(lis)
	i = l - 1
	prod = 1
	print(prod, end=' ')
while i != -1:
	prod = prod * lis[i]
	print(prod, end=' ')
	i = i - 1


(n, _) = map(int, input().split())
k = list(map(int, input().split()))
k.sort(reverse=True)

def solve(x, solution):
	if x == 1:
		return tuple(reversed(solution + (x,)))
	for i in k:
		if x % i == 0:
			a = solve(x // i, solution + (x,))
			if a:
				return a
	return None
solution = solve(n, tuple())
if solution:
	print(' '.join((str(x) for x in solution)))
else:
	print(-1)


[N, K] = input().strip().split(' ')
[N, K] = [int(N), int(K)]
a = list(input().strip().split(' '))
a = [int(e) for e in a]
a = sorted(a, reverse=True)
i = 0
b = []
while N > 1 and i < len(a):
	while N % a[i] == 0:
		N = N / a[i]
		b.append(a[i])
	i = i + 1
b = sorted(b)
if int(N) == 1:
	op = []
	op.append(1)
	for i in range(len(b)):
		op.append(op[len(op) - 1] * b[i])
	print(*op)
else:
	print('-1')


def menorLexicografico(list1, list2):
	m = len(list1)
	n = len(list2)
	if n == 0 or (m != 0 and m < n):
		return list1
	elif m == 0 or (n != 0 and m > n):
		return list2
	else:
		for i in range(m):
			if list1[i] < list2[i]:
				return list1
			elif list1[i] > list2[i]:
				return list2
		return list1

def kFactorization(sequence, k, n, result):
	result.append(n)
	if n == 1:
		return (True, result)
	if n > 1:
		result_copy = result[:]
		result = []
		for i in range(k - 1, -1, -1):
			if n % sequence[i] == 0:
				result2 = result_copy[:]
				(noFallo, result2) = kFactorization(sequence[0:i + 1], i + 1, n // sequence[i], result2)
				if noFallo:
					result = menorLexicografico(result, result2)
	if len(result) > 0:
		return (True, result)
	else:
		return (False, [])
(n, k) = [int(s) for s in input().split()]
sequence = [int(s) for s in input().split()]
sequence = sorted(sequence)
result = []
(noFallo, result) = kFactorization(sequence, k, n, result)
if noFallo:
	print(' '.join((str(v) for v in result[::-1])))
else:
	print(-1)


import sys
from typing import List, Optional, Set

def isqrt(n: int) -> int:
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def factorize(n: int) -> Set[int]:
	factors = {n}
	for i in range(2, isqrt(n) + 1):
		if n % i == 0:
			factors.add(i)
			factors.add(n // i)
	return factors

def _k_factorize(n: int, factors: List[int], lexical_factors: List[int]) -> Optional[List[int]]:
	if n <= 1:
		return sorted(lexical_factors)
	if not factors:
		return None
	first_factor = factors[0]
	if n % first_factor == 0:
		new_lexical_factors = lexical_factors[:]
		new_lexical_factors.append(first_factor)
		result = _k_factorize(n // first_factor, factors, new_lexical_factors)
		if result:
			return result
	return _k_factorize(n, factors[1:], lexical_factors)

def k_factorize(n: int, factors: List[int]) -> List[int]:
	actual_factors = factorize(n)
	revised_factors = []
	lexical_factors = [1]
	for f in factors:
		if f in actual_factors:
			revised_factors.append(f)
	result = _k_factorize(n, sorted(revised_factors, reverse=True), [])
	print('result: {}'.format(result), file=sys.stderr)
	if result:
		total = 1
		for x in result:
			total *= x
			lexical_factors.append(total)
		return lexical_factors
	return [-1]

def main():
	(n, _) = [int(x) for x in input().strip().split()]
	factors = [int(x) for x in input().strip().split()]
	print(*k_factorize(n, factors))
main()


import sys

def KFac(n, k, arr):
	result = [1]
	state = rec(n, arr, k, 0, [])
	state.reverse()
	for i in state:
		result.append(i * result[-1])
	if result == [1]:
		return -1
	else:
		return ' '.join(map(str, result))

def rec(n, arr, k, pt, state):
	if n == 1:
		return state
	elif pt >= k:
		return []
	i = arr[pt]
	if n % i == 0:
		arr1 = state.copy()
		arr2 = state.copy()
		arr1.append(i)
		r1 = rec(n // i, arr, k, pt, arr1)
		r2 = rec(n, arr, k, pt + 1, arr2)
		r1_len = len(r1)
		r2_len = len(r2)
		if r1_len <= 0:
			if r2_len <= 0:
				return []
			else:
				return r2
		elif r2_len <= 0:
			return r1
		else:
			return r1 if r1_len <= r2_len else r2
	else:
		return rec(n, arr, k, pt + 1, state)
(N, K) = input().split()
A = sorted([int(c) for c in input().split()], reverse=True)
print(KFac(int(N), int(K), A))


(a, n1) = map(int, input().split(' '))
s = list(map(int, input().split(' ')))
s.sort(reverse=True)
a1 = []
a2 = a
for i in s:
	x = 0
	if a % i == 0:
		while a % i == 0:
			a //= i
			x += 1
	a1.append([i, x])
a1.reverse()
n = 1
s1 = '1 '
for i in a1:
	for j in range(i[1]):
		n *= i[0]
		s1 += str(n) + ' '
if not int(s1.strip().split(' ')[-1]) == a2:
	print(-1)
else:
	print(s1)


(n, k) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
a.sort()
nodes = {}
wave = [n] if n > 1 else []
deep = 0
while len(wave) > 0:
	deep += 1
	xwave = []
	for w in wave:
		for ak in a:
			if w % ak != 0:
				continue
			m = w // ak
			if not m in nodes:
				nodes[m] = (deep, w)
				xwave.append(m)
				continue
			if (deep, w) >= nodes[m]:
				continue
			nodes[m] = (deep, w)
	wave = xwave
if n == 1:
	print(1)
elif not 1 in nodes:
	print(-1)
else:
	path = [1]
	m = 1
	while m < n:
		m = nodes[m][1]
		path.append(m)
	print(' '.join((str(m) for m in path)))


def fun(arr, n, k):
	a = []
	i = 0
	while n != 1 and i < k:
		if n % arr[i] == 0:
			a.append(n)
			n = n // arr[i]
		else:
			i += 1
	if n != 1:
		return [-1]
	a.append(1)
	return a
(n, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
arr.sort(reverse=True)
a = fun(arr, n, k)[::-1]
print(*a, sep=' ')


(n, _) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))

def f(n, a):
	b = sorted([i for i in a if n % i == 0], reverse=True)
	if n == 1:
		return [1]
	if b == []:
		return [-1]
	m = max(b)
	return [n] + f(n // m, b)
t = f(n, a)
if t[-1] == -1:
	print(-1)
else:
	print(' '.join([str(i) for i in t[::-1]]))


(n, k) = list(map(int, input().split()))
a = [int(x) for x in input().split() if n % int(x) == 0]
a.sort()
b = []
i = len(a) - 1
while n > 1 and i > -1:
	while n > 1 and n % a[i] == 0:
		b += [a[i]]
		n //= a[i]
	i -= 1
if n != 1:
	print('-1')
else:
	k = 1
	print('1', end=' ')
	for j in reversed(b):
		k *= j
		print(k, end=' ')
	print('')


import sys

def print_dbg(*objects):
	print(*objects, file=sys.stderr)
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
solution = [n]
i = k - 1
while i >= 0:
	if n % a[i] == 0:
		n //= a[i]
		solution.append(n)
	else:
		i -= 1
solution = solution[::-1]
print_dbg(*solution)
if solution[0] != 1:
	print(-1)
else:
	print(*solution)


(N, K) = list(map(int, input().strip().split(' ')))
ar = list(map(int, input().strip().split(' ')))

def aux(n, l, arr):
	if n == 1:
		return []
	for i in range(l):
		if n % arr[i] == 0:
			re = aux(n // arr[i], l, arr)
			if re != -1:
				return [arr[i]] + re
	return -1
ar.sort(reverse=True)
res = aux(N, K, ar)
if res == -1:
	print(-1)
else:
	res.sort()
	count = 1
	s = '1 '
	for i in res:
		count = count * i
		s = s + str(count) + ' '
	print(s)


def factor(n, arr, dicti):
	if n in dicti:
		return dicti[n]
	else:
		test = []
		testl = []
		for i in arr:
			if n % i == 0:
				if n // i == 1:
					return [1, n]
				else:
					temp = factor(n // i, arr, dicti)
					if temp != [-1]:
						test.append(temp + [n])
						testl.append(len(temp) + 1)
		if len(test) == 0:
			return [-1]
		else:
			minvalue = min(testl)
			minarr = ''
			for i in range(0, len(test)):
				if testl[i] == minvalue:
					test[i].sort()
					if minarr == '':
						minarr = test[i]
					else:
						for j in range(1, minvalue):
							if test[i][j] < minarr[j]:
								minarr = test[i]
								break
							elif test[i][j] > minarr[j]:
								break
			dicti[n] = minarr
			return minarr
(n, k) = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
dicti = {}
print(*factor(n, arr, dicti))


def kfactor(n, arr):
	j = n
	result = []
	while True:
		signal = False
		for num in sorted(arr, reverse=True):
			if j % num == 0:
				result.append(j)
				j = j // num
				signal = True
				break
			if j == 1:
				result.append(1)
				return list(reversed(result))
		if not signal:
			return [-1]

def main():
	(n, k) = map(int, input().strip().split())
	a = tuple(map(int, input().split()))
	result = kfactor(n, a)
	print(*result)
main()


import sys
from itertools import zip_longest

def test(n, ff):

	def gen(n, ff):
		ff = list(reversed(sorted(ff)))
		stack = [(1, [])]
		while stack:
			(u, aa) = stack.pop()
			if u == n:
				yield aa
			elif u < n:
				for f in ff:
					stack.append((u * f, aa + [f]))
	print('n=%d ff=%s' % (n, ff), file=sys.stderr)
	cc = None
	for aa in gen(n, ff):
		if cc is None or len(aa) < len(cc):
			cc = aa
	if cc is None:
		return [-1]
	rval = [1]
	for c in cc:
		rval.append(rval[-1] * c)
	return rval

def solve(n, ff):
	cache = {1: []}
	ff = list(reversed(sorted(ff)))
	print('n=%d ff=%s' % (n, ff), file=sys.stderr)

	def calc(n):
		if n in cache:
			return cache[n]
		rval = None
		for f in ff:
			if n % f == 0:
				uu = calc(n // f)
				if uu is not None:
					uu = uu + [f]
					if rval is None:
						rval = uu
					elif len(uu) < len(rval):
						rval = uu
					elif len(uu) == len(rval):
						ls = True
						for (a, b) in zip(rval, uu):
							if a > b:
								ls = False
								break
						if ls:
							rval = uu
		cache[n] = rval
		return rval
	cc = calc(n)
	if cc is None:
		return [-1]
	rval = [1]
	for c in cc:
		rval.append(rval[-1] * c)
	return rval
(n, _) = map(int, input().split())
ff = list(map(int, input().split()))
vv = solve(n, ff)
for v in vv:
	print(v, end=' ')
print()


import sys
(n, l) = map(int, input().strip().split(' '))
d = list(map(int, input().strip().split(' ')))
d = sorted(d, reverse=True)
i = 0
m = 1
p1 = []
p1.append(n)
while n > 1 and i < l:
	v = d[i]
	if n % v == 0:
		n = n / v
		p1.append(int(n))
	else:
		i = i + 1
z = 1
if z not in p1:
	p1.append(1)
p1 = p1[::-1]
if len(p1) > 1 and p1[1] in d:
	print(' '.join((str(l) for l in p1)))
else:
	print('-1')


from itertools import accumulate

def k_factorizer(n, k, A):
	optimal_state = get_optimal_state(n, k, A)
	if optimal_state == -1:
		return -1
	else:
		optimal_factors = k_factorizer0(n, k, A, 0, optimal_state)
		assert optimal_factors != None
		optimal_factors.insert(0, 1)
		assert all((f1 <= f2 for (f1, f2) in zip(optimal_factors, optimal_factors[1:])))
		ans = list(accumulate(optimal_factors, func=lambda x, y: x * y))
		return ' '.join(map(str, ans))

def get_optimal_state(n, k, A):
	factors = []
	for a in sorted(A, reverse=True):
		if n == 1:
			break
		while n > 1 and n % a == 0:
			factors.append(a)
			n //= a
	if n > 1:
		return -1
	return len(factors)

def k_factorizer0(n, k, A, i, optimal_state):
	if i >= k:
		return None
	if optimal_state == 1:
		if n in A:
			return [n]
		else:
			return None
	a = A[i]
	if n % a == 0:
		prev_ans = k_factorizer0(n // a, k, A, i, optimal_state - 1)
		if prev_ans != None:
			return [a] + prev_ans
	return k_factorizer0(n, k, A, i + 1, optimal_state)

def main():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A = [a for a in set(A) if n % a == 0]
	A.sort()
	print(k_factorizer(n, len(A), A))
main()


def func(a, n, l, k, n1):
	if n == 1:
		l2 = l[::-1]
		l2.append(n1)
		for x in l2:
			print(x, end=' ')
		return
	if k == 0:
		print(-1)
		return
	elif n % a[k - 1] == 0:
		l.append(int(n / a[k - 1]))
		if n / a[k - 1] % a[k - 1] == 0:
			func(a[:k], n / a[k - 1], l, k, n1)
		else:
			func(a[:k - 1], n / a[k - 1], l, k - 1, n1)
	else:
		func(a[:k - 1], n, l, k - 1, n1)
inp = input()
(n, k) = [int(x) for x in inp.split()]
inp1 = input()
a = [int(x) for x in inp1.split()]
a.sort()
l = []
n1 = n
l1 = func(a, n, l, k, n1)


def get_less(a, b):
	if len(a) < len(b):
		return a
	elif len(a) > len(b):
		return b
	else:
		for i in range(len(a)):
			if a[i] < b[i]:
				return a
			elif a[i] > b[i]:
				return b
		return a

def calculateWays(cur_res, N, ar, way, best_way):
	if cur_res == N:
		return way
	elif cur_res > N:
		return []
	elif len(best_way) > 0 and len(way) > len(best_way):
		return []
	for i in range(len(ar)):
		res = calculateWays(cur_res * ar[i], N, ar[i:], way + [cur_res * ar[i]], best_way)
		if len(res) > 0:
			if len(best_way) == 0:
				best_way = res
			else:
				best_way = get_less(best_way, res)
	return best_way
(N, _) = [int(x) for x in input().split()]
ar = sorted([int(x) for x in input().split()])
res = calculateWays(1, N, ar, [1], [])
if len(res) > 0:
	print(*res, sep=' ')
else:
	print(-1)


import sys
(n, size_a) = input().strip().split(' ')
n = int(n)
a = list(map(int, input().strip().split(' ')))
a = sorted(a)

def division_order(n, a):
	if n == 1:
		return []
	if len(a) == 0:
		return -1
	while n % a[0] != 0:
		a.pop(0)
		if len(a) == 0:
			return -1
	b = a[1:len(a)]
	div1 = division_order(n / a[0], a[:])
	if div1 != -1:
		div1 = [a[0]] + div1
	if len(b) >= 1:
		div2 = division_order(n, b)
	else:
		div2 = -1
	if div1 == -1 and div2 == -1:
		return -1
	if div1 == -1:
		return div2
	if div2 == -1:
		return div1
	if len(div1) <= len(div2):
		return div1
	else:
		return div2
div_ord = division_order(n, a)
if div_ord == -1:
	print(div_ord)
else:
	path = [1]
	for i in div_ord:
		path.append(path[-1] * i)
	print(*path, sep=' ')


N = [int(s) for s in input().split(' ')][0]
A = [int(s) for s in input().split(' ')]
A.sort()
p = [N]
A = A[::-1]
for k in A:
	while N % k == 0:
		N /= k
		p.append(N)
if p[-1] != 1:
	print(-1)
else:
	print(' '.join(map(lambda v: str(int(v)), p[::-1])))


def fracto(num, setFrac):
	setFrac.sort()
	res = [num]
	while len(setFrac) != 0 and num != 1:
		if num % setFrac[-1] != 0:
			setFrac.pop()
		else:
			res = [num // setFrac[-1]] + res
			num //= setFrac[-1]
	if num != 1:
		return [-1]
	if len(res) == 1:
		res.pop()
		res.append(-1)
	return res
(num, tmp) = input().split(' ')
setFrac = [int(i) for i in input().split(' ')]
res = fracto(int(num), setFrac)
for i in res:
	print(i, end=' ')


x = input().split(' ')
val = int(x[0])
length = int(x[1])
array = input().split(' ')
array = sorted((int(elem) for elem in array))[::-1]
solution = list()
solution.append(val)
while val != 1:
	new_val = val
	for elem in array:
		if val % elem == 0:
			new_val /= elem
			solution.append(new_val)
			break
	if new_val == val:
		break
	else:
		val = new_val
if val != 1:
	print(-1)
else:
	for elem in solution[::-1]:
		print(int(elem), end=' ')


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
n_t = n
s = []
unsolvable = False
while n_t > 1:
	f = False
	for i in a:
		if n_t % i == 0:
			n_t = n_t / i
			s.append(i)
			f = True
	if not f:
		print(-1)
		unsolvable = True
		break
if not unsolvable:
	s.sort()
	r = [1]
	m = 1
	for i in s:
		m *= i
		r.append(m)
	print(' '.join(map(str, r)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def f(ar, x):
	if x == 1:
		return []
	if len(ar) == 0:
		return [-1]
	d = []
	while x % ar[-1] == 0:
		x /= ar[-1]
		d.append(ar[-1])
	return d + f(ar[:-1], x)
e = f(a, n)
if -1 in e:
	print(-1)
else:
	e.sort()
	q = 1
	print(q, end=' ')
	for i in e:
		q *= i
		print(q, end=' ')


import sys
from typing import List, Optional, Set

def isqrt(n: int) -> int:
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def factorize(n: int) -> Set[int]:
	factors = {n}
	for i in range(2, isqrt(n) + 1):
		if n % i == 0:
			factors.add(i)
			factors.add(n // i)
	return factors

def _k_factorize(n: int, factors: List[int], lexical_factors: List[int]) -> Optional[List[int]]:
	if n <= 1:
		return sorted(lexical_factors)
	if not factors:
		return None
	first_factor = factors[0]
	if n % first_factor == 0:
		new_lexical_factors = lexical_factors[:]
		new_lexical_factors.append(first_factor)
		result = _k_factorize(n // first_factor, factors, new_lexical_factors)
		if result:
			return result
	return _k_factorize(n, factors[1:], lexical_factors)

def k_factorize(n: int, factors: List[int]) -> List[int]:
	trimmed_factors = []
	lexical_series = [1]
	for f in factors:
		if n % f == 0:
			trimmed_factors.append(f)
	result = _k_factorize(n, sorted(trimmed_factors, reverse=True), [])
	if result:
		total = 1
		for x in result:
			total *= x
			lexical_series.append(total)
		return lexical_series
	return [-1]

def main():
	(n, _) = [int(x) for x in input().strip().split()]
	factors = [int(x) for x in input().strip().split()]
	print(*k_factorize(n, factors))
main()


(n, k) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
l.sort(reverse=True)

def fac(l, n):
	o = []
	i = 0
	if n == 1:
		print(-1)
	while n != 1 and i < len(l):
		e = l[i]
		while n % e == 0:
			o.append(e)
			n //= e
		i += 1
	if n != 1:
		print(-1)
	else:
		o.append(1)
		o = o[::-1]
		c = 1
		for i in range(len(o)):
			c *= o[i]
			print(c, end=' ')
fac(l, n)


n = int(input().strip().split(' ')[0])
factors = sorted(list(map(int, reversed(input().strip().split(' ')))))
i = len(factors) - 1
stack = []
while i >= 0:
	res = n
	cur = i
	while cur >= 0:
		factor = factors[cur]
		if not res % factor:
			stack.append(res)
			res = res // factor
			if res == 1:
				stack.append(1)
				print(' '.join(map(str, reversed(stack))))
				i = -1
				cur = -1
			else:
				cur = i
		else:
			cur -= 1
	if i != -1:
		stack = []
	i -= 1
if len(stack) == 0:
	print('-1')


[N, K] = input().split()
N = int(N)
K = int(K)
a = [int(x) for x in input().split()]
a.sort()

def k_factor(N, a, K, mylist):
	if N in a:
		return mylist + [N]
	for k in reversed(range(K)):
		if N % a[k] == 0:
			ans = k_factor(int(N / a[k]), a, K, mylist + [a[k]])
			if ans != -1:
				return ans
	return -1
factors = k_factor(N, a, K, [1])
if factors != -1:
	factors.sort()
	for i in range(len(factors)):
		if i != 0:
			factors[i] *= factors[i - 1]
	print(*factors, sep=' ')
else:
	print(-1)


def rec(n, fac, ctr, arr):
	if ctr >= len(fac) and n != 1:
		return -1
	elif n == 1:
		return arr
	elif n % fac[ctr] == 0:
		arr.append(fac[ctr])
		n = n / fac[ctr]
		return rec(n, fac, ctr, arr)
	elif n % fac[ctr] != 0:
		return rec(n, fac, ctr + 1, arr)
(n, k) = input().split(' ')
(n, k) = (int(n), int(k))
fac = list(map(int, input().split(' ')))
fac.sort()
fac.reverse()
ans = rec(n, fac, 0, [])
if ans == -1:
	print(ans)
else:
	ans.sort()
	temp = 1
	print(temp, end=' ')
	for j in ans:
		temp = temp * j
		print(temp, end=' ')


def solve_greedy(numbers, target):
	numbers.sort(reverse=True)
	r = target
	res = [target]
	i = 0
	while i < len(numbers):
		if r % numbers[i] == 0:
			r //= numbers[i]
			res.append(r)
			if r == 1:
				return reversed(res)
			continue
		i += 1
	return [-1]
n = int(input().split()[0])
nums = list(map(int, input().split()))
print(*solve_greedy(nums, n))


def min_steps(x):
	if x > n:
		return [float('inf'), '']
	if x == n:
		return [0, '']
	if x in dic:
		return dic[x]
	r = float('inf')
	s = ''
	for i in range(k):
		if a[i] * x > n:
			break
		[t1, t2] = min_steps(x * a[i])
		t1 += 1
		if r > t1:
			r = t1
			s = str(a[i] * x) + ' ' + t2
	dic[x] = [r, s]
	return [r, s]
[n, k] = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
dic = {}
if min_steps(1)[0] == float('inf'):
	print(-1)
else:
	print('1 ' + min_steps(1)[1])


import sys
way = []
(n, k) = list(map(int, input().strip().split(' ')))
ar = list(map(int, input().strip().split(' ')))
ar = sorted(ar)
ar = ar[::-1]

def rec(a):
	if a in ar:
		way.append(1)
		way.append(n)
		sway = sorted(way)
		for c in sway:
			print(c, end=' ')
		sys.exit()
	else:
		for x in ar:
			if a % x == 0:
				way.append(int(a / x))
				rec(a / x)
rec(n)
print('-1')


import sys

def k_factorization(arr, idx, k, n, result):
	for i in range(k):
		if n % arr[i] != 0:
			continue
		num = n // arr[i]
		result.append(arr[i])
		k_factorization(arr, i, k, num, result)
		return result

def get_minimum_list(arr):
	min_len = sys.maxsize
	for r in arr:
		if min_len > len(r):
			min_len = len(r)
			min_list = r
		elif min_len == len(r):
			min_list = min(min_list, r)
	return min_list

def display_result(min_list, n):
	answer = [1]
	num = 1
	for m in min_list:
		num *= m
		answer.append(num)
	if answer[-1] != n:
		print(-1)
	else:
		print(' '.join(map(str, answer)))

def main():
	(n, k) = list(map(int, input().strip().split()))
	arr = sorted(list(map(int, input().strip().split())), reverse=True)
	result_k_fac = []
	for i in range(k):
		if n % arr[i] != 0:
			continue
		num = n // arr[i]
		ret = k_factorization(arr, i, k, num, [arr[i]])
		if ret is None:
			continue
		result_k_fac.append(sorted(ret))
	if len(result_k_fac) == 0:
		print(-1)
		sys.exit(1)
	min_list = get_minimum_list(result_k_fac)
	display_result(min_list, n)
main()


(n, k) = [int(x) for x in input().split()]
ps = sorted([int(x) for x in input().split()])
seen = [[1]]
for p in ps:
	newseen = seen[:]
	for states in seen:
		fin = states[-1]
		res = states[:]
		while fin < n and n % fin == 0:
			fin *= p
			res = res + [fin]
			newseen.append(res)
	seen = newseen
res = []
for states in seen:
	if states[-1] == n:
		res.append(states)
print(' '.join(map(str, min(res, key=lambda s: (len(s), s)))) if res else -1)


(number, _) = [int(x) for x in input().split()]
factors = sorted((int(x) for x in input().split()), reverse=True)
answer = []
for factor in factors:
	while number % factor == 0:
		answer.insert(0, factor)
		number //= factor
if number > 1:
	print(-1)
else:
	result = [1]
	for a in answer:
		result.append(result[-1] * a)
	print(' '.join(map(str, result)))


(N, K) = [int(el) for el in input().strip().split(' ')]
arr = [int(el) for el in input().strip().split(' ')]
arr.sort()
res = []
idx = len(arr) - 1
while idx >= 0:
	div = arr[idx]
	while N % div == 0:
		res.append(div)
		N /= div
	idx -= 1
if N != 1:
	print(-1)
else:
	res.sort()
	prod = 1
	res_arr = [str(1)]
	for el in res:
		prod *= el
		res_arr.append(str(prod))
	print(' '.join(res_arr))


(n, k) = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
arr = []
flag = 0
cp = n
while n != 1:
	i = 0
	while i < k and n % s[i] != 0:
		i += 1
	if i != k:
		arr.append(n // s[i])
		n = n // s[i]
	else:
		break
if n != 1:
	print(-1)
else:
	print(*arr[::-1], cp)


(n, k) = input().split()
[n, k] = list(map(int, [n, k]))
factors = list(map(int, input().split()))
factors.sort(key=lambda x: x)
factors = factors[::-1]
useful = []
for x in factors:
	while n % x == 0:
		n /= x
		useful.append(x)
	if n == 1:
		break
useful = useful[::-1]
if n != 1:
	print(-1)
else:
	ans = '1'
	temp = 1
	for x in useful:
		temp *= x
		ans += ' ' + str(temp)
	print(ans)


def kFact(n, a):
	if n == 1:
		return [int(n)]
	else:
		for factor in a:
			if n % factor == 0:
				return kFact(n / factor, a) + [int(n)]
		return [-1]
(n, k) = [int(temp) for temp in input().split()]
a = sorted([int(temp) for temp in input().split()], reverse=True)
result = kFact(n, a)
if -1 in result:
	print(-1)
else:
	print(*result)


def k_factorize(n, k, arr):
	result = [n]
	arr.sort()
	desc = arr[::-1]
	i = 0
	while i < k:
		div = n / desc[i]
		if div == 1:
			result.append(div)
			result = list(map(int, result))
			result = list(map(str, result))
			return ' '.join(result[::-1])
		elif int(div) == div and div > 1:
			result.append(div)
			n = div
		else:
			i += 1
	return -1
(n, k) = input().split(' ')
(n, k) = (int(n), int(k))
arr = input().split(' ')
arr = [int(val) for val in arr]
result = k_factorize(n, k, arr)
print(result)


from collections import defaultdict

def fact(n, idx, el, a):
	if n == 1:
		el.append(1)
		return True
	for i in range(idx, -1, -1):
		if n % a[i] == 0:
			if fact(n / a[i], i, el, a):
				el.append(a[i])
				return True
	return False
(n, k) = list(map(int, input().split()))
el = list(map(int, input().split()))
el = sorted(el)
sol = []
if not fact(n, len(el) - 1, sol, el):
	print(-1)
else:
	slo = 1
	for x in sol:
		slo *= x
		print(slo, end=' ')


def findDivisors(np):
	if np == 1:
		return True
	else:
		for x in A:
			if np % x == 0:
				states.append(np // x)
				return findDivisors(np // x)
		return False
(n, k) = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
A.sort(reverse=True)
states = [n]
s = findDivisors(n)
if s:
	states.sort()
	print(' '.join([str(x) for x in states]))
else:
	print(-1)


goal = int(input().strip().split(' ')[0])
vals = input().strip().split(' ')
goal = int(goal)
for i in range(len(vals)):
	vals[i] = int(vals[i])
vals.sort()

def revFactor(goal, vals):
	storage = [goal]
	for val in reversed(vals):
		while goal % val == 0:
			goal = goal // val
			storage.append(goal)
	if goal != 1:
		print(-1)
	else:
		storage.reverse()
		for i in range(len(storage)):
			storage[i] = str(storage[i])
		print(' '.join(storage))
revFactor(goal, vals)


def solve(a, n, res):
	res.append(n)
	if n == 1:
		print(' '.join(map(str, reversed(res))))
		exit(0)
	if len(a) == 0:
		return
	for i in range(len(a)):
		if n % a[i] == 0:
			solve(a, n // a[i], res)
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
solve(a, n, [])
print('-1')


import os
(n, m) = input().strip('').split()
n = int(n)
m = int(m)
l = list(map(int, input().split()))
l.sort()
ans = 1
l1 = []
for i in range(0, len(l)):
	if n % l[i] == 0:
		l1.append(l[i])
j = len(l1) - 1
l3 = []
while j >= 0:
	if n % (ans * l1[j]) == 0 and ans <= n:
		ans = ans * l1[j]
		l3.append(l1[j])
	else:
		j = j - 1
test = 1
for t in range(0, len(l3)):
	test = test * l3[t]
if test == n:
	k = len(l3) - 1
	ans = 1
	while k >= 0:
		print(ans, end=' ')
		ans = ans * l3[k]
		k = k - 1
	print(ans, end=' ')
else:
	print(-1)


import sys
from typing import List, Optional, Set

def isqrt(n: int) -> int:
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def factorize(n: int) -> Set[int]:
	factors = {n}
	for i in range(2, isqrt(n) + 1):
		if n % i == 0:
			factors.add(i)
			factors.add(n // i)
	return factors

def _k_factorize(n: int, factors: List[int], lexical_factors: List[int]) -> Optional[List[int]]:
	if n <= 1:
		return sorted(lexical_factors)
	if not factors:
		return None
	first_factor = factors[0]
	if n % first_factor == 0:
		new_lexical_factors = lexical_factors[:]
		new_lexical_factors.append(first_factor)
		result = _k_factorize(n // first_factor, factors, new_lexical_factors)
		if result:
			return result
	return _k_factorize(n, factors[1:], lexical_factors)

def k_factorize(n: int, factors: List[int]) -> List[int]:
	trimmed_factors = []
	lexical_series = [1]
	for f in factors:
		if n % f == 0:
			trimmed_factors.append(f)
	result = _k_factorize(n, sorted(trimmed_factors, reverse=True), [])
	if result:
		total = 1
		for x in result:
			total *= x
			lexical_series.append(total)
		return lexical_series
	return [-1]

def main():
	(n, _) = [int(x) for x in input().strip().split()]
	factors = [int(x) for x in input().strip().split()]
	print(*k_factorize(n, factors))
main()


def smaller(a, b):
	if len(a) < len(b):
		return a
	if len(b) < len(a):
		return b
	for i in range(len(a)):
		if a[i] < b[i]:
			return a
		elif b[i] < a[i]:
			return b

def to_seq(a, path):
	output = [1]
	for i in range(k):
		x = a[i]
		for _ in range(path[i]):
			output.append(output[-1] * x)
	return ' '.join(map(str, output))

def solve(n, a, path, curr=1, i=0):
	if i >= len(a):
		return to_seq(a, path) if curr == n else None
	p = 0
	x = 1
	res = None
	while curr * x <= n:
		path.append(p)
		r = solve(n, a, path, curr * x, i + 1)
		if r != None:
			if res == None or smaller(res, r) == r:
				res = r
			else:
				return res
		path.pop()
		p += 1
		x = a[i] ** p
	return res
(n, k) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
a.sort()
path = []
res = solve(n, a, path)
if res != None:
	print(res)
else:
	print(-1)


l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
l1.sort()
l2 = []
l3 = []
b = l[0]
while l[0] != 1:
	list(map(lambda x: l[0] % x == 0 and l2.append(x), l1))
	if l2 == []:
		l3 = []
		break
	a = l2[-1]
	l[0] = l[0] // a
	l3.append(str(l[0]))
	l2 = []
if l3 == []:
	print('-1')
else:
	l3 = l3[::-1] + [str(b)]
	print(' '.join(l3))


[x, n] = [int(num) for num in input().split(' ')]
lst0 = sorted((int(num) for num in input().split(' ')))[::-1]
lst = [num for num in lst0 if x % num == 0]

def factorize(x, lst, state):
	if x == 1:
		return ' '.join(state[::-1])
	else:
		for i in range(len(lst)):
			if x % lst[i] == 0:
				x2 = x // lst[i]
				state.append(str(x2))
				return factorize(x2, lst, state)
			else:
				pass
		if len(state) < 1:
			return '-1'
out = factorize(x, lst, [])
if out == '-1' or out == None:
	print(-1)
else:
	print(factorize(x, lst, []), x)


def KFact(N, array):
	array.sort(reverse=True)
	sol = [N]
	for i in range(len(array)):
		while N % array[i] == 0:
			N = N // array[i]
			sol.append(N)
		if N == 1:
			break
	sol.sort()
	if sol[0] != 1:
		return [-1]
	else:
		return sol
(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
A = list(map(int, input().strip().split(' ')))
print(*KFact(N, A))