Mike và Bài toán GCD

Trong một chuyến đi công viên, FullHouse Dev gặp một bài toán thú vị về GCD (Ước số chung lớn nhất). Với tinh thần ham học hỏi, họ quyết định cùng nhau giải quyết bài toán này.

Bài toán

Cho một mảng \(A\) có \(N\) phần tử (đánh số từ 1). Khoảng cách giữa hai chỉ số \(i\) và \(j\) được tính bằng \(|i-j|\). Với mỗi chỉ số \(i\) (từ 1 đến \(N\)), cần tìm một chỉ số \(j\) thỏa mãn:

• \(i \neq j\)
• GCD(\(A[i], A[j]\)) > 1
• Khoảng cách giữa \(i\) và \(j\) là nhỏ nhất

Nếu có nhiều chỉ số \(j\) thỏa mãn điều kiện trên, chọn chỉ số \(j\) nhỏ nhất.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(N\) - kích thước của mảng \(A\)
• Dòng thứ hai chứa \(N\) số nguyên, trong đó số thứ \(i\) biểu diễn \(A[i]\)

OUTPUT FORMAT:

• In ra \(N\) số nguyên, trong đó số thứ \(i\) là chỉ số \(j\) thỏa mãn các điều kiện trên
• Nếu không tồn tại chỉ số \(j\) thỏa mãn, in ra -1

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

5
2 3 4 9 17

OUTPUT

3 4 1 2 -1

Giải thích

• Với chỉ số 1, chỉ số gần nhất thỏa mãn là 3, vì GCD(2,4)=2 > 1
• Tương tự, với các chỉ số 2, 3, và 4, các chỉ số gần nhất thỏa mãn lần lượt là 4, 1, và 2
• Với chỉ số 5, không có chỉ số nào thỏa mãn điều kiện nên in ra -1