codeforces#P1468L. Prime Divisors Selection

    ID: 31730 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>binary searchgreedymathnumber theory*2700

Prime Divisors Selection

Description

Suppose you have a sequence of $k$ integers $A = [a_1, a_2, \dots , a_k]$ where each $a_i \geq 2$. A sequence of prime integers $P = [p_1, p_2, \dots, p_k]$ is called suitable for the sequence $A$ if $a_1$ is divisible by $p_1$, $a_2$ is divisible by $p_2$ and so on.

A sequence of prime integers $P$ is called friendly if there are no unique integers in this sequence.

A sequence $A$ is called ideal, if each sequence $P$ that is suitable for $A$ is friendly as well (i. e. there is no sequence $P$ that is suitable for $A$, but not friendly). For example, the sequence $[2, 4, 16]$ is ideal, while the sequence $[2, 4, 6]$ is not ideal (there exists a sequence $P = [2, 2, 3]$ which is suitable for $A$, but not friendly).

You are given $n$ different integers $x_1$, $x_2$, ..., $x_n$. You have to choose exactly $k$ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 1000$).

The second line contains $n$ pairwise distinct integers $x_1$, $x_2$, ..., $x_n$ ($2 \leq x_i \leq 10^{18}$).

If it is impossible to choose exactly $k$ integers from $x_1$, $x_2$, ..., $x_n$ in such a way that the chosen integers form an ideal sequence, print $0$.

Otherwise, print $k$ pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

Input

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 1000$).

The second line contains $n$ pairwise distinct integers $x_1$, $x_2$, ..., $x_n$ ($2 \leq x_i \leq 10^{18}$).

Output

If it is impossible to choose exactly $k$ integers from $x_1$, $x_2$, ..., $x_n$ in such a way that the chosen integers form an ideal sequence, print $0$.

Otherwise, print $k$ pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

Samples

3 3
2 4 6

0

3 3
2 4 16

2 4 16 

4 3
2 4 6 16

2 4 16