F. Эла и GCD и простые числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После долгого, тяжелого, но плодотворного дня в DTL Эла счастливая возвращается домой. Она отдыхает, решая задачи по соревновательному программированию. Сейчас она предпочитает короткие условия, потому что на работе уже прочитала слишком много кода и документации.

Вам дано целое число $$$c$$$. Предположим, что $$$c$$$ имеет $$$n$$$ делителей. Вам нужно найти последовательность из $$$n - 1$$$ целого числа $$$[a_1, a_2, ... a_{n - 1}]$$$, удовлетворяющую следующим условиям:

  • Каждый элемент последовательности строго больше $$$1$$$.
  • Каждый элемент последовательности является делителем $$$c$$$.
  • Все элементы последовательности различны.
  • Для всех $$$1 \le i < n - 1$$$ $$$\gcd(a_i, a_{i + 1})$$$ является простым числом.

В этой задаче, так как число $$$c$$$ может быть слишком большим, задано не само число $$$c$$$, а его факторизация.

$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) целых чисел $$$x$$$ и $$$y$$$, а простое число — это натуральное число, имеющее ровно $$$2$$$ делителя.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Каждый набор входных данных состоит из двух строк. В первой строке каждого набора входных данных дано одно целое число $$$m$$$ ($$$1 \le m \le 16$$$) — количество простых множителей $$$c$$$.

Вторая строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i < 2^{20}$$$)  — показатели степени входящих в $$$c$$$ простых чисел, так что $$$c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m}$$$ и $$$n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1)$$$. $$$p_i$$$ — $$$i$$$-е наименьшее простое число.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.

Выходные данные

Выведите ответ для каждого теста, по одному в строке. Если искомой последовательности для данного $$$c$$$ не существует, выведите $$$-1$$$.

В противном случае, выведите $$$n - 1$$$ строк. В $$$i$$$-й строке выведите через пробел $$$m$$$ целых чисел. $$$j$$$-е целое число $$$i$$$-й строки равно показателю степени $$$j$$$-го простого числа для $$$a_i$$$.

Если ответов несколько, выведите любой из них.

Пример
Входные данные
5
2
1 1
1
1
3
1 1 1
1
4
2
2 1
Выходные данные
0 1 
1 1 
1 0 
1 
0 1 1 
0 0 1 
1 0 1 
1 1 0 
0 1 0 
1 1 1 
1 0 0 
-1
2 0 
1 1 
0 1 
2 1 
1 0
Примечание

В наборах входных данных значения $$$c$$$ равны $$$6$$$, $$$2$$$, $$$30$$$, $$$16$$$ и $$$12$$$ в указанном порядке.

В первом наборе входных данных $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$ являются делителями числа $$$6$$$. Подходящие последовательности — $$$[2, 6, 3]$$$ и $$$[3, 6, 2]$$$. Например, перестановка $$$[3, 2, 6]$$$ не подходит, поскольку $$$\gcd(a_1, a_2) = 1$$$ не является простым числом.

В четвертом наборе входных данных $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$, $$$16$$$ являются делителями числа $$$16$$$. Среди перестановок последовательности $$$[2, 4, 8, 16]$$$ не существует ответа.