У Shohag есть целое число \(n\) и множество \(S\) из \(m\) различных целых чисел. Помогите ему найти лексикографически наибольший\(^{\text{∗}}\) массив целых чисел \(a_1, a_2, \ldots, a_n\) такой, что \(a_i \in S\) для каждого \(1 \le i \le n\), а также для всех пар \(1 \le i \lt j \le n\) должно выполняться \(a_{\operatorname{gcd}(i, j)} \neq \operatorname{gcd}(a_i, a_j)\)\(^{\text{†}}\). Или скажите, что таких массивов не существует.
Выходные данные
Для каждого набора входных данных, если нет решения, выведите \(-1\). Иначе выведите \(n\) целых чисел — лексикографически наибольший массив, удовлетворяющий условиям.
Примечание
В первом наборе входных данных каждый элемент массива принадлежит заданному множеству \(S = \{3, 4, 6\}\), а все пары индексов массива удовлетворяют необходимым условиям. В частности, для пары \((2, 3)\): \(a_{\operatorname{gcd}(2, 3)} = a_1 = 6\) и \(\operatorname{gcd}(a_2, a_3) = \operatorname{gcd}(4, 4) = 4\), поэтому они не равны. Существуют и другие массивы, удовлетворяющие условиям, но этот — лексикографически наибольший.
В третьем наборе входных данных массива не существует, так как возможно только \(a = [2, 2]\), но для этого массива для пары \((1, 2)\) имеем: \(a_{\operatorname{gcd}(1, 2)} = a_1 = 2\) и \(\operatorname{gcd}(a_1, a_2) = \operatorname{gcd}(2, 2) = 2\), то есть они равны, что недопустимо!
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 3
3 4 6
1 1
1
2 1
2
|
6 4 4 3 4 3
1
-1
|