Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.
Перестановка {p
1, p
2, …, p
n} будет лексикографически меньше перестановки {q
1, q
2, …, q
n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p
j = q
j при j < i и p
i < q
i.
В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.
Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.
Входные данные
Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 10
9). Вторая строка содержит n различных натуральных чисел, не превосходящих 10
9. Все числа в строках разделены пробелом.
Выходные данные
В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 1 2
6 8 3 9 |
3 9 6 8 |
| 2 |
4 4 2
6 8 3 9 |
9 3 6 8 |
| 3 |
4 5 2
6 8 3 9 |
-1 |