Chef and The Divisibility Queries

All submissions for this problem are available.
The Chef is given a sequence of N integers A_{1}, A_{2}, ..., 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_{1}, A_{2}, ..., 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^{5})
 1 ≤ A_{i} ≤ 100000 (10^{5})
 1 ≤ L ≤ R ≤ N
 1 ≤ K ≤ 100000 (10^{5})
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
Author:  rustinpiece 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/DIVQUERY 
Tags  cook37, medium, offlineprocess, rustinpiece 
Date Added:  10082013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 