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