Preparing NOJ

# Recover it!

4000ms 262144K

## Description:

Authors guessed an array $a$ consisting of $n$ integers; each integer is not less than $2$ and not greater than $2 \cdot 10^5$. You don't know the array $a$, but you know the array $b$ which is formed from it with the following sequence of operations:

1. Firstly, let the array $b$ be equal to the array $a$;
2. Secondly, for each $i$ from $1$ to $n$:
• if $a_i$ is a prime number, then one integer $p_{a_i}$ is appended to array $b$, where $p$ is an infinite sequence of prime numbers ($2, 3, 5, \dots$);
• otherwise (if $a_i$ is not a prime number), the greatest divisor of $a_i$ which is not equal to $a_i$ is appended to $b$;
3. Then the obtained array of length $2n$ is shuffled and given to you in the input.

Here $p_{a_i}$ means the $a_i$-th prime number. The first prime $p_1 = 2$, the second one is $p_2 = 3$, and so on.

Your task is to recover any suitable array $a$ that forms the given array $b$. It is guaranteed that the answer exists (so the array $b$ is obtained from some suitable array $a$). If there are multiple answers, you can print any.

## Input:

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $2n$ integers $b_1, b_2, \dots, b_{2n}$ ($2 \le b_i \le 2750131$), where $b_i$ is the $i$-th element of $b$. $2750131$ is the $199999$-th prime number.

## Output:

In the only line of the output print $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 2 \cdot 10^5$) in any order — the array $a$ from which the array $b$ can be obtained using the sequence of moves given in the problem statement. If there are multiple answers, you can print any.

## Sample Input:

 3 3 5 2 3 2 4

## Sample Output:

 3 4 2

## Sample Input:

 1 2750131 199999

## Sample Output:

 199999

## Sample Input:

 1 3 6

## Sample Output:

 6

Info

Provider CodeForces

Code CF1176D

Tags

dfs and similargraphsgreedynumber theorysortings

Submitted 81

Passed 41

AC Rate 50.62%

Date 07/21/2019 13:41:35

Related

Nothing Yet