You are given a sequence $a_1, a_2, \ldots, a_n$ consisting of positive integers. You have to answer $q$ queries. A query is defined by a triplet of numbers $(l, r, x)$. For each query, you have to find the largest $p$ such that $l \le p \le r$ and $a_p$ is coprime with $x$, or determine that there is no such $p$.

Two numbers are coprime if the only positive integer that divides both of them is 1.

Input

The first line of the input contains two integers $n$ and $q$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

The next $q$ lines contain queries. The $i$-th of these lines contains three integers $l_i$, $r_i$ and $x_i$.

Output

For each query, output the largest such $p$ if it exists. Otherwise output -1.

Constraints

• $1 \le n, q \le 10^5$
• $1 \le a_i \le 10^5$
• $1 \le l_i \le r_i \le n$
• $1 \le x \le 10^5$

Example

Input:

5 4
1 2 3 4 6
1 5 2
1 1 1
4 5 2
3 5 3

Output:

3
1
-1
4