#P1176D. Recover it!
Recover it!
No submission language available for this problem.
Description
Authors guessed an array consisting of integers; each integer is not less than and not greater than . You don't know the array , but you know the array which is formed from it with the following sequence of operations:
- Firstly, let the array be equal to the array ;
- Secondly, for each from to :
- if is a prime number, then one integer is appended to array , where is an infinite sequence of prime numbers ();
- otherwise (if is not a prime number), the greatest divisor of which is not equal to is appended to ;
- Then the obtained array of length is shuffled and given to you in the input.
Here means the -th prime number. The first prime , the second one is , and so on.
Your task is to recover any suitable array that forms the given array . It is guaranteed that the answer exists (so the array is obtained from some suitable array ). If there are multiple answers, you can print any.
The first line of the input contains one integer () — the number of elements in .
The second line of the input contains integers (), where is the -th element of . is the -th prime number.
In the only line of the output print integers () in any order — the array from which the array can be obtained using the sequence of moves given in the problem statement. If there are multiple answers, you can print any.
Input
The first line of the input contains one integer () — the number of elements in .
The second line of the input contains integers (), where is the -th element of . is the -th prime number.
Output
In the only line of the output print integers () in any order — the array from which the array can be obtained using the sequence of moves given in the problem statement. If there are multiple answers, you can print any.