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:

• First line contains two space-separated integers $N$ and $Q$
• Next line contains $N$ space-separated integers denoting the array $A$.
• Next line contains $Q$ space-separated integers denoting the queries.

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$