Problem
Dado un conjunto de n números naturales diferentes. Una permutación de elementos de este conjunto se denomina k-permutación si para dos elementos vecinos cualesquiera de esta permutación su máximo común divisor es al menos k. Por ejemplo, si se da el conjunto de elementos S = {6, 3, 9, 8}, entonces la permutación {8, 6, 3, 9} es una permutación de 2 y la permutación {6, 8, 3, 9} – No.
La permutación {p
1, p
2, …, p
n} será lexicográficamente menor que la permutación {q
1< /sub>, q2, …, qn} si existe un entero positivo i (1 ≤ i ≤ n) tal que pj = qj cuando j < i y pi < qi.
Como ejemplo, ordenemos todas las k-permutaciones del conjunto anterior en orden lexicográfico. Por ejemplo, hay exactamente cuatro permutaciones de 2 de S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} y {9, 3, 6 , 8} . En consecuencia, la primera permutación de 2 en el orden lexicográfico es el conjunto {3, 9, 6, 8}, y la cuarta – establecer {9, 3, 6, 8}.
Debe escribir un programa que le permita encontrar la m-ésima k-permutación en este orden.
Entrada
El archivo de entrada en la primera línea contiene tres números naturales – n (1 ≤ n ≤ 16), m y k (1 ≤ m, k ≤ 109). La segunda línea contiene n números naturales distintos que no superan 109. Todos los números en las líneas están separados por espacios.
Impresión
Es necesario generar la m-ésima k-permutación del conjunto dado o –1 si no hay ninguna en el archivo de salida.
Ejemplos
| # |
Entrada |
Salida |
| 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 |