Divisible LCM

adnan_toky Criterion 2022 Round 16
Limits 1s, 512 MB

You have a sequence a1, a2, a3, , ana_1,~ a_2,~ a_3,~…, ~a_n of n integers and qq queries. In each query, you are given three integers ll, rr and xx. You have to answer the following question:

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

Here LCM means the Least Common Multiple of numbers.

Input

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

The next line contains nn space-separated integers a1, a2, a3, , ana_1, ~a_2, ~a_3,~…, ~a_n (1ai105)(1 \leq a_i \leq 10^5).

Following qq lines contain three integers each. ll, rr and xx (1lrn,1x105)(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

InputOutput
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

Submit

Login to submit.

Statistics

50% Solution Ratio
adnan_tokyEarliest, 6M ago
adnan_tokyFastest, 0.4s
adnan_tokyLightest, 14 MB
adnan_tokyShortest, 2292B
Toph uses cookies. By continuing you agree to our Cookie Policy.