Module: Patterns in Dynamic Programming - 2


Problem

5 /5


Permutations

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 {p1, p2, …, pn} will be lexicographically less than the permutation {q1, q2, …, qn} if there exists a positive integer i (1 ≤ i ≤ n) such that pj= qj when j < i and pi < qi.

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 ≤ 109). The second line contains n distinct natural numbers not exceeding 109. 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