Description

One day，Little-Y saw many numbers standing in a row. A question suddenly appeared in her mind, ”From the L-th number to the R-th number, how many of them is a mutiple of P ? (P is a prime number) , and how quickly can I settle this problem ? ”

Input

Mutiple test cases. Please process till the end of file.
For each test case：
The first line contains two positive integers n and q (1<=n,q<=10^5), which means there are n integers standing in a row and q queries followed.
The second line contains n positive integers, a1,a2,a3,…,an (no more than 10^6) . Here, ai means the i-th integer in the row.
The next are q queries, each of which takes one line. For each query, there are three integers L,R,P (1<=L<=R<=n, 1<=P<=10^6, P is gurantteed to be a prime number). Their meanings have been mentioned in the discription.

Output

For each query, output the answer in one line.

Sample Input

6 5
12 8 17 15 90 28
1 4 3
2 6 5
1 1 2
3 5 17
1 6 999983

Sample Output

2
2
1
1
0

HINT

?

Source

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include