Permutations
Problem
Soit un ensemble de n nombres naturels différents. Une permutation d'éléments de cet ensemble est appelée une k-permutation si pour deux éléments voisins de cette permutation leur plus grand commun diviseur est au moins k. Par exemple, si l'ensemble des éléments S = {6, 3, 9, 8} est donné, alors la permutation {8, 6, 3, 9} est une 2-permutation, et la permutation {6, 8, 3, 9} – non.
La permutation {p
1, p
2, …, p
n} sera lexicographiquement inférieure à la permutation {q
1< /sub>, q2, …, qn} s'il existe un entier positif i (1 ≤ i ≤ n) tel que pj = qj quand j < je et pje < qje.
A titre d'exemple, ordonnons toutes les k-permutations de l'ensemble ci-dessus dans l'ordre lexicographique. Par exemple, il y a exactement quatre 2-permutations de S : {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} et {9, 3, 6 , 8} . En conséquence, la première 2-permutation dans l'ordre lexicographique est l'ensemble {3, 9, 6, 8}, et la quatrième – définir {9, 3, 6, 8}.
Vous devez écrire un programme qui vous permette de trouver la m-ième k-permutation dans cet ordre.
Entrée
Le fichier d'entrée de la première ligne contient trois nombres naturels – n (1 ≤ n ≤ 16), m et k (1 ≤ m, k ≤ 109). La deuxième ligne contient n nombres naturels distincts n'excédant pas 109. Tous les nombres dans les lignes sont séparés par des espaces.
Mentions légales
Il est nécessaire de sortir la m-ième k-permutation de l'ensemble donné ou –1 s'il n'y en a pas dans le fichier de sortie.
Exemples
| # |
Entrée |
Sortie |
| 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 |