Question
Find Closest Coprime Stone
You have a row of ancient stones, each labeled with a number. For each stone at position i, you must find another stone at position j such that the greatest common divisor (GCD) of their numbers is 1, and the distance between them is as small as possible. If there are two stones at the same distance, choose the one with the smaller position. If no such stone exists, return -1. Your task is to figure out the closest matching stone for each one in the row.
Input
The first line of the input contains a single integer N.
The next line of the input contains N space-separated integers, the elements of the array A.
Constraints
1 ≤ N ≤ 200000
1 ≤ A[i] ≤ 50
The next line of the input contains N space-separated integers, the elements of the array A.
Constraints
1 ≤ N ≤ 200000
1 ≤ A[i] ≤ 50
Output
Output N space separated integers, the value of j corresponding to each index. If there is no possible value of j, output -1 instead.
Example
Sample Input
5
1 2 4 3 9
Sample Output
1 1 4 3 3
Explanation
For index 1, gcd(A[1], A[1]) = 1, and abs(1-1) = 0.
For index 2, gcd(A[2], A[1]) = 1, and abs(2-1) = 1. gcd(A[2], A[4) is also equal to 1, but abs(2-4) = 2, which is a greater value.
Similarly for index 3, 4, and 5, gcd(A[3], A[4]) = 1, gcd(A[4], A[3]) = 1, and gcd(A[5], A[3]) = 1.
5
1 2 4 3 9
Sample Output
1 1 4 3 3
Explanation
For index 1, gcd(A[1], A[1]) = 1, and abs(1-1) = 0.
For index 2, gcd(A[2], A[1]) = 1, and abs(2-1) = 1. gcd(A[2], A[4) is also equal to 1, but abs(2-4) = 2, which is a greater value.
Similarly for index 3, 4, and 5, gcd(A[3], A[4]) = 1, gcd(A[4], A[3]) = 1, and gcd(A[5], A[3]) = 1.