Problem
Given a set of n different natural numbers. A permutation of elements of this set is called a k-permutation if for any two neighboring elements of this permutation their greatest common divisor is at least k. For example, if the set of elements S = {6, 3, 9, 8} is given, then the permutation {8, 6, 3, 9} is a 2-permutation, and the permutation {6, 8, 3, 9} – no.
The permutation {p
1, p
2, …, p
n} will be lexicographically less than the permutation {q
1, q
2, …, q
n} if there exists a positive integer i (1 ≤ i ≤ n) such that p
j= q
j when j < i and p
i < q
i.
As an example, let's order all k-permutations of the above set in lexicographic order. For example, there are exactly four 2-permutations of S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3}, and {9, 3, 6, 8} . Accordingly, the first 2-permutation in the lexicographic order is the set {3, 9, 6, 8}, and the fourth – set {9, 3, 6, 8}.
You are required to write a program that allows you to find the m-th k-permutation in this order.
Input
The input file in the first line contains three natural numbers – n (1 ≤ n ≤ 16), m and k (1 ≤ m, k ≤ 10
9). The second line contains n distinct natural numbers not exceeding 10
9. All numbers in the lines are separated by spaces.
Imprint
It is necessary to output the m-th k-permutation of the given set or –1 if there is none in the output file.
Examples
| # |
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 |