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

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

4 1 2
6 8 3 9

3 9 6 8

4 4 2
6 8 3 9

9 3 6 8

4 5 2
6 8 3 9

-1

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