Given an array \(A\) of \(N\) integers. You are given \(Q\) queries of the following type:-

\(x\) : Find the farthest index say \(j\) in the array \(A\) from index \(x\) such that \(A[x]\) and \(A[j]\) are coprime. If there exists more then one index, print the smallest one. If there does not exist any such index, print \(-1\).

Two numbers are said to be coprime if the only common factor between them is \(1\).

Input Format:

Output Format:

Print \(Q\) space-separated integers denoting the answer to the queries.

Constraints:

\(1 \le N, Q \le 10^5 \\ 1 \le A[i] \le 10^3 \\ 1 \leq x\leq N\)