21682번 - Перестановки 다국어

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = { 6, 3, 9, 8 }, то перестановка { 8, 6, 3, 9 } является 2-перестановкой, а перестановка { 6, 8, 3, 9 } – нет.

Перестановка { p₁, p₂, …, p_n } лексикографически меньше перестановки { q₁, q₂, …, 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⁹). Вторая строка содержит n различных натуральных чисел не превосходящих 10⁹.

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