 | После долгого, тяжелого, но плодотворного дня в 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\) делителя.
Выходные данные
Выведите ответ для каждого теста, по одному в строке. Если искомой последовательности для данного \(c\) не существует, выведите \(-1\).
В противном случае, выведите \(n - 1\) строк. В \(i\)-й строке выведите через пробел \(m\) целых чисел. \(j\)-е целое число \(i\)-й строки равно показателю степени \(j\)-го простого числа для \(a_i\).
Если ответов несколько, выведите любой из них.
Примечание
В наборах входных данных значения \(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]\) не существует ответа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|