Given an array $A$ of $n$ positive integers. The distance between two elements $i$ and $j$ is defined as $|i - j|$. For each element $i$ in the array, find the element $j$ closest to $i$ such that $\text{gcd}(A_i, A_j) \neq 1$.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print $n$ integers, where the $i$-th integer represents the position of the element closest to $i$ satisfying the condition. If no such element exists, print `-1`. If there are two satisfying indices, print the smaller index.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le A_i \le 10^6$.
### Example
Input:
```
5
2 3 4 9 17
```
Output:
```
3 4 1 2 -1
```
