给定一个包含 $n$ 个正整数的序列 $a_1, a_2, \dots, a_n$。你需要回答 $q$ 个询问。每个询问由一个三元组 $(l, r, x)$ 定义。对于每个询问，你需要找到最大的 $p$，使得 $l \le p \le r$ 且 $a_p$ 与 $x$ 互质，或者确定不存在这样的 $p$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100\,000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100\,000$)。 接下来的 $q$ 行包含询问。第 $i$ 行包含三个整数 $l_i, r_i$ 和 $x_i$ ($1 \le l_i \le r_i \le n, 1 \le x_i \le 100\,000$)。

输出格式

对于每个询问，在单独的一行中输出答案。

样例

样例输入 1

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

样例输出 1

3
1
-1
4