Processing math: 100%

Задача D. Перестановки с НОД

Автор:Рекомендации   Ограничение времени: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 (1in), для которого 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}.

Примечание

Решения, работающие только для n10, будут оцениваться из 50 баллов.

Формат входного файла

Входной файла содержит целые числа числа — nmk, за которыми следуют n различных натуральных чисел si.

Формат выходного файла

Выходной файл должен содержать m-ую k-перестановку заданного множества или 1, если такой нет.

Ограничения

1n16

1m,k,si109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
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

0.064s 0.008s 13