Module: Padrões em Programação Dinâmica - 2

Problem

Dado um conjunto de n números naturais diferentes. Uma permutação de elementos desse conjunto é chamada de k-permutação se, para quaisquer dois elementos vizinhos dessa permutação, seu maior divisor comum for pelo menos k. Por exemplo, se o conjunto de elementos S = {6, 3, 9, 8} é dado, então a permutação {8, 6, 3, 9} é uma permutação 2, e a permutação {6, 8, 3, 9} – não.

A permutação {p₁, p₂, …, p_n} será lexicograficamente menor que a permutação {q1< /sub>, q₂, …, q_n} se existe um inteiro positivo i (1 ≤ i ≤ n) tal que p_j = q_j quando j < i e p_i < q_i.

Como exemplo, vamos ordenar todas as k-permutações do conjunto acima em ordem lexicográfica. Por exemplo, existem exatamente quatro 2-permutações de S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} e {9, 3, 6 , 8} . Assim, a primeira 2-permutação na ordem lexicográfica é o conjunto {3, 9, 6, 8}, e a quarta – definir {9, 3, 6, 8}.

Você precisa escrever um programa que permita encontrar a m-ésima k-permutação nessa ordem.

Entrada
O arquivo de entrada na primeira linha contém três números naturais – n (1 ≤ n ≤ 16), m e k (1 ≤ m, k ≤ 10⁹). A segunda linha contém n números naturais distintos que não excedem 10⁹. Todos os números nas linhas são separados por espaços.

Impressão
É necessário gerar a m-ésima k-permutação do conjunto fornecido ou –1 se não houver nenhum no arquivo de saída.

Exemplos

#	Entrada	Saída
1	4 1 2 6 8 3 9	3 9 6 8
2	4 4 2 6 8 3 9	9 3 6 8
3	4 5 2 6 8 3 9	-1