Problem
n 個の異なる自然数のセットが与えられる。このセットの要素の並べ替えは、この並べ替えの任意の 2 つの隣接する要素の最大公約数が少なくとも k である場合、k-並べ替えと呼ばれます。たとえば、要素のセット S = {6, 3, 9, 8} が与えられた場合、順列 {8, 6, 3, 9} は 2 順列であり、順列 {6, 8, 3, 9} –いいえ
順列 {p
1, p
2, …, p
n} は、辞書順に順列 {q
1< より小さくなります。 /sub>, q2, …, qn} pj となるような正の整数 i (1 ≤ i ≤ n) が存在する場合= qj の場合、j <; i と pi <; qi.
例として、上記のセットのすべての k 順列を辞書順に並べてみましょう。たとえば、S の 2 順列はちょうど 4 つあります: {3, 9, 6, 8}、{8, 6, 3, 9}、{8, 6, 9, 3}、および {9, 3, 6 、８｝。したがって、辞書編集順の最初の 2 順列は集合 {3, 9, 6, 8} であり、4 番目の – は集合 {3, 9, 6, 8} です。 {9、3、6、8} を設定します。
この順序でm番目のk順列を見つけることができるプログラムを書く必要があります。
入力
入力ファイルの最初の行には 3 つの自然数が含まれています。 n (1 ≤ n ≤ 16)、m および k (1 ≤ m、k ≤ 109)。 2 行目には、109 を超えない n 個の異なる自然数が含まれています。行内のすべての数字はスペースで区切られています。
インプリント
指定されたセットの m 番目の k 順列を出力する必要があります。出力ファイルに存在しない場合は -1 を出力する必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 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 |