서로소 질의

양의 정수로 이루어진 수열 $a_1, a_2, \ldots, a_n$이 주어진다. $q$개의 질의에 답해야 한다. 각 질의는 세 정수 $(l, r, x)$로 주어진다. 각 질의에 대해 $l \leq p \leq r$을 만족하고 $a_p$가 $x$와 서로소인 가장 큰 $p$를 구한다. 그런 $p$가 없으면 없다고 판정한다.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \leq n, q \leq 100\,000$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \leq a_i \leq 100\,000$).

이어지는 $q$개의 줄에는 각각 세 정수 $l_i$, $r_i$, $x_i$가 주어진다 ($1 \leq l_i \leq r_i \leq n$, $1 \leq x_i \leq 100\,000$).

각 질의의 답을 한 줄에 하나씩 출력한다. 그런 $p$가 없으면 $-1$을 출력한다.