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

Условие

Задано множество из 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}.

Примечание

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

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

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

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

Ограничения

1 ≤ n ≤ 16

1 ≤ m, k, s_i ≤ 10⁹

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

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