Problem
n개의 서로 다른 자연수 집합이 주어집니다. 이 집합의 요소에 대한 순열은 이 순열의 이웃하는 두 요소의 최대 공약수가 적어도 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에는 {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} 및 {9, 3, 6과 같이 정확히 4개의 2-순열이 있습니다. , 8} . 따라서 사전식 순서의 첫 번째 2 순열은 {3, 9, 6, 8} 집합이고 네 번째 -ndash; {9, 3, 6, 8}을 설정합니다.
이 순서대로 m번째 k 순열을 찾는 프로그램을 작성해야 합니다.
입력
첫 번째 줄의 입력 파일에는 세 개의 자연수 – n(1 < n < 16), m 및 k(1 < m, k < 109). 두 번째 줄에는 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 |