Problem
Diberi satu set n nombor asli yang berbeza. Pilih atur unsur set ini dipanggil pilih atur k jika bagi mana-mana dua unsur berjiran pilih atur ini pembahagi sepunya terbesar mereka ialah sekurang-kurangnya k. Sebagai contoh, jika set unsur S = {6, 3, 9, 8} diberikan, maka pilih atur {8, 6, 3, 9} ialah pilih atur 2, dan pilih atur {6, 8, 3, 9} – tidak.
Pilih atur {p
1, p
2, …, p
n} secara leksikografi akan kurang daripada pilih atur {q
1< /sub>, q2, …, qn} jika wujud integer positif i (1 ≤ i ≤ n) supaya pj = qj apabila j < i dan pi < qi.
Sebagai contoh, mari kita susun semua permutasi k bagi set di atas dalam susunan leksikografi. Sebagai contoh, terdapat betul-betul empat pilih atur 2 S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3}, dan {9, 3, 6 , 8} . Oleh itu, pilih atur 2 pertama dalam susunan leksikografi ialah set {3, 9, 6, 8} dan &ndash keempat; tetapkan {9, 3, 6, 8}.
Anda dikehendaki menulis atur cara yang membolehkan anda mencari permutasi ke-m dalam susunan ini.
Input
Fail input dalam baris pertama mengandungi tiga nombor asli – n (1 ≤ n ≤ 16), m dan k (1 ≤ m, k ≤ 109). Baris kedua mengandungi n nombor semula jadi berbeza tidak melebihi 109. Semua nombor dalam baris dipisahkan dengan ruang.
Cetakan
Ia adalah perlu untuk mengeluarkan permutasi ke-m bagi set yang diberikan atau –1 jika tiada dalam fail output.
Contoh
| # |
Input |
Output |
| 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 |