The Chef is given a sequence of N integers A₁, A₂, ..., A_N. He has to process Q queries on the above sequence. Each query is represented by three integers:

• L R K => report cardinality of { i : K divides A_i, L ≤ i ≤ R }. In other words, how many integers in the subsequence starting at L^th element and ending at R^th element are divisible by K.

Input

The first line of the input contains two space separated integer N and Q.
The following line contains N space separated integers giving the sequence A₁, A₂, ..., A_N.
Then there will be Q lines each containing three space separated integers L R K, representing a query.

Output

For each query output the result in one line.

Constraints

• 1 ≤ N, Q ≤ 100000 (10⁵)
• 1 ≤ A_i ≤ 100000 (10⁵)
• 1 ≤ L ≤ R ≤ N
• 1 ≤ K ≤ 100000 (10⁵)

Example

Input:
8 5
3 5 1 4 6 9 12 6
3 6 2
3 6 4
4 8 3
2 6 7
8 8 6

Output:
2
1
4
0
1

size of 10^5 gives an idea of initially  finding factors of all array elements in nsqrt(n) times.

We use a vector to push all the indexes where k occurs.

Now we , simply store them in a 2d vector and then binary search on it to give the answer.

#include<bits/stdc++.h>
using namespace std;
vector<int> fact[100010];
int arr[100010];

int main()
{
 int n;
 cin>>n;
 int q;
 cin>>q;
 
 for(int i=1;i<=n;i++)
 {
   scanf("%d",&arr[i]);
 }
 for(int i=1;i<=n;i++)
 {
    int val=sqrt(arr[i]);
    for(int j=1;j<=val;j++)
    {
       if(arr[i]%j==0)
       {
            fact[j].push_back(i);
            if(j!=arr[i]/j)
            fact[arr[i]/j].push_back(i);
    }
    }
 }
 

    while(q--)
    {
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        vector<int> ::iterator low,high;
        
        low=lower_bound(fact[k].begin(),fact[k].end(),l);
        high=upper_bound(fact[k].begin(),fact[k].end(),r);
        int ans=high-low;
        cout<<ans<<endl;
    }
 return 0;
}