Автор: | Рекомендации | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt | |||
Максимальный балл: | 100 |
Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S= {6,3,9,8}, то перестановка {8,6,3,9} является 2-перестановкой, а перестановка {6,8,3,9} — нет.
Перестановка {p1,p2,…,pn} будет лексикографически меньше перестановки {q1,q2,…,qn}, если существует такое натуральное число i (1≤i≤n), для которого pj=qj при j<i и pi<qi.
В качестве примера упорядочим все 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}.
Входной файла содержит целые числа числа — nmk, за которыми следуют n различных натуральных чисел si.
Выходной файл должен содержать m-ую k-перестановку заданного множества или −1, если такой нет.
1≤n≤16
1≤m,k,si≤109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|