printОбластная олимпиада школьников по информатике

print8. Перестановки

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Задано множество из `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`, если такой нет.
Примеры входных и выходных данных

input.txt

4 1 2
6 8 3 9

output.txt

3 9 6 8

input.txt

4 4 2
6 8 3 9

output.txt

9 3 6 8

input.txt

4 5 2
6 8 3 9

output.txt

-1
Примечание
Решения, работающие только для `n ≤ 10`, будут оцениваться из 50 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/
loading