Problem Q: Child prodigy FFT

Problem Q: Child prodigy FFT

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 211  Solved: 19
[Submit] [Status] [Web Board] [Creator:]

Description

fft小弟弟对数学特别喜欢,但是他的口算能力不是特别好,有一天他找到了数学神童FFT,FFT现在要来测试一下fft小弟弟的口算水平。FFT给了fft小弟弟n个数,a[1],a[2],a[3]....a[n],以及q个问题,每个问题给出三个整数(l,r,d),

他要询问fft小弟弟,在n个数里,a[l]*a[l + 1]*a[l + 2]...a[r - 1]*a[r]是否是可以整除d的,如果可以整除,则回答“YeS”,否则回答“No”

你可以帮fft小弟弟解决这个问题吗??

Input

第一行输入测试数据的组数 t (1 <= t <= 10)

每组数据的第一行输入n,q,代表数的个数和问题的个数(1 <= n <= 100000 , 1 <= q <= 100000)

第二行是n个整数,代表的是a[i]序列 (1 <= a[i] <= 100000)

接下来 q 行,输入 l,r,d 代表的问题查询,对于每一个问题,输出一个结果(1 <= l <= r <= n,1 <= d <= 100000)

Output

对于每次问题,输出一个结果

Sample Input Copy

1
5 5
2 7 3 4 5 
1 3 21
2 3 18
4 5 18
2 3 7
3 5 35

Sample Output Copy

YeS
No
No
YeS
No