Divisible LCM

You have a sequence $a_1,~ a_2,~ a_3,~…, ~a_n$ of n integers and $q$ queries. In each query, you are given three integers $l$, $r$ and $x$. You have to answer the following question:

Is it possible to select some integers from the segment $a_l,~ a_{l+1}, ~a_{l+2},~\dots~ a_r$ such that their LCM is divisible by $x$ and no two consecutive integers are selected? That is, if you select $a_i$, you cannot select $a_{i+1}$.

Here LCM means the Least Common Multiple of numbers.

Input

The first line of input contains two space-separated integers $n$ and $q$ $(1 \leq n, q \leq 10^5)$ denoting the number of integers and the number of queries.

The next line contains $n$ space-separated integers $a_1, ~a_2, ~a_3,~…, ~a_n$ $(1 \leq a_i \leq 10^5)$.

Following $q$ lines contain three integers each. $l$, $r$ and $x$ $(1 \leq l \leq r \leq n, 1 \leq x \leq 10^5)$.

Output

For each query, print Yes or No in a single line, the answer to the query.

Sample

6 5
4 7 3 5 12 22
1 5 10
2 5 10
5 5 12
3 5 10
1 4 20

Yes
No
Yes
No
Yes