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 gcd(Ai,Aj)≠1.
### Input
- The first line contains an integer n.
- The second line contains n integers Ai.
### 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≤n≤105.
- 1≤Ai≤106.
### Example
Input:
5234917
Output:
3412-1