eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Задано множество из 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 (1in), для которого 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-перестановку в этом порядке.

Giriş verilənləri

Первая строка содержит три натуральных числа n (1 n 16), mи k (1 m, k 10^9). Вторая строка содержитnразличных натуральных чисел, не превосходящих 10^9.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1 1 1
1
Çıxış verilənləri #1
1
Mənbə 2009 Областная олимпиада школьников по информатике, Вологда, Задача H