Permutations

Given a set of $n$ distinct positive integers. A permutation of the elements of this set is called a $k$-permutation if, for any two adjacent elements in the permutation, their greatest common divisor is at least $k$. For example, if the given set S = \{6,\ 3,\ 9,\ 8\}, the permutation \{8, 6, 3, 9\} is a $2$-permutation, but \{6, 8, 3, 9\} is not.

The permutation \{p_1, p_2, \dots, p_n\} is lexicographically smaller than the permutation \{q_1, q_2, \dots, q_n\} if there exists an integer $i$ (1 \leq i \leq n) such that p_j = q_j for all j < i, and p_i < q_i.

For example, let us list all $k$-permutations of the set above in lexicographical order. There are exactly four $2$-permutations of set $S$: \{3, 9, 6, 8\}, \{8, 6, 3, 9\}, \{8, 6, 9, 3\}, and \{9, 3, 6, 8\}. Thus, the first $2$-permutation in lexicographical order is \{3, 9, 6, 8\}, and the fourth is \{9, 3, 6, 8\}.

Write a program that finds the $m$-th $k$-permutation in this order.