2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
L. Prime Divisors Selection

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputSuppose 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.

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.

Examples

Input

3 3

2 4 6

Output

0

Input

3 3

2 4 16

Output

2 4 16

Input

4 3

2 4 6 16

Output

2 4 16

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 05:00:21 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|