Permutazioni
Problem
Dato un insieme di n numeri naturali diversi. Una permutazione di elementi di questo insieme è chiamata k-permutazione se per due qualsiasi elementi vicini di questa permutazione il loro massimo comune divisore è almeno k. Ad esempio, se viene dato l'insieme di elementi S = {6, 3, 9, 8}, la permutazione {8, 6, 3, 9} è una permutazione 2 e la permutazione {6, 8, 3, 9} – n.
La permutazione {p
1, p
2, …, p
n} sarà lessicograficamente minore della permutazione {q
1< /sub>, q2, …, qn} se esiste un intero positivo i (1 ≤ i ≤ n) tale che pj = qj quando j < i e pi < qi.
Ad esempio, ordiniamo tutte le k-permutazioni dell'insieme precedente in ordine lessicografico. Ad esempio, ci sono esattamente quattro 2-permutazioni di S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} e {9, 3, 6 , 8} . Di conseguenza, la prima 2-permutazione nell'ordine lessicografico è l'insieme {3, 9, 6, 8}, e la quarta – imposta {9, 3, 6, 8}.
Devi scrivere un programma che ti permetta di trovare la m-esima k-permutazione in questo ordine.
Inserimento
Il file di input nella prima riga contiene tre numeri naturali – n (1 ≤ n ≤ 16), m e k (1 ≤ m, k ≤ 109). La seconda riga contiene n numeri naturali distinti non superiori a 109. Tutti i numeri nelle righe sono separati da spazi.
Impressum
È necessario emettere la m-esima k-permutazione dell'insieme dato o –1 se non ce n'è nessuna nel file di output.
Esempi
| # |
Input |
Uscita |
| 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 |