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

CodeForces

Provider CodeForces

Origin Codeforces Round #565 (Div. 3)

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