Задача 40085. Permutations

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₁, p₂, …, p_n} will be lexicographically less than the permutation {q₁, q₂, …, 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⁹). The second line contains n distinct natural numbers not exceeding 10⁹. 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