594. Kingdom Festival and Non-Coprime Numbers

0

Hard

Once upon a time, in a kingdom ruled by a wise and just king, there was a desire to foster unity and harmony among the various tribes. To achieve this, a grand festival was planned where everyone could come together and celebrate.

In preparation for the festival, the king's advisors were tasked with gathering supplies and resources from all corners of the kingdom. Among these resources were bags of stones, each containing a different number of stones.

However, the king's mathematician noticed that some of the bags contained numbers that were not coprime. In other words, there were adjacent numbers in the bag that shared a common factor other than 1.

Realizing that this could cause issues, the mathematician took action. He replaced the two adjacent numbers in each bag with their LCM (Least Common Multiple). This process was repeated for all bags with non-coprime numbers until there were no more left.

As the mathematician worked, he realized that this process could be generalized. He wanted to create an algorithm that could identify and replace non-coprime numbers in any given array of integers. This algorithm would ensure that all resources gathered for the festival were coprime, promoting unity and harmony among the tribes.

Can you assist the mathematician in solving this problem?

Input Format

The first line of input contains the size of the array, n. The next line contains n space-separated integers representing the elements of the array.

Output Format

Return the modified array as a space-separated list of integers.

Example

Input

7 2 2 1 1 3 3 3

Output

2 1 1 3

Constraints

1 <= arr.length <= 105
1 <= arr[i] <= 105