NAJ0001  Divisible Number Sum
Hazzat is a new guys in computer science. Now he read in 4rd semester. Recently he completed the course data structure. After finished data structure course he can realize that those are not enough for his. Every day he fall in a new (data structure) problem and want solve it, but those problem he can’t solve using his know data structure. He want to establish new data structure. But he always failed to establish it. Now help hazzat to establish a new data structure following problems.
You will be given an array A of N integers. You need to answer M queries.
Each query is of the form V x y.
For each query, find the sum of set S which is a sub set of array A index x to y and fully divisible by V.
That means find sum of set S (subset of A), where A[i] is included in S if x ≤ i ≤ y and A[i]%V==0.
Input:
First line consists of a number T (1 ≤ T ≤ 5) test cases.
For each case given two integer number N M, (1≤ N≤ 10^5, 1≤M ≤ 2*10^5)
Next line has N integers representing the elements of array A. 1≤A[]≤ 10^6
M lines follow, one per query.
Each line has 3 integers V, x and y (1≤ V ≤ 1000 , 1≤ x ≤ y ≤N)
Output:
For each case print Case No and query answer.
There will be a blank line between two cases.
Sample:
Input 
Output 
2 
Case #1 
Hints:
Query 1:
In array index 1 to 5 the set S is {2,4,6} because those are fully divisible by 2. so sum is 12
Query 2:
In array index 1 to 4 the set S is {} because there are not any number which fully divisible by 5. so sum is 0
Data set is so huge. Use faster I/O
hide comments
[Lakshman]:
20150420 13:59:14
AC nice one. Last edit: 20150420 16:40:05 

mjh:
20141215 08:59:08
any hint for tle? 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141106 19:28:33
Seems that SPOJ has bug on counting peak memory usage. It print final memory usage only, it not counting memory usage that have been deallocated before my program terminate.

Added by:  Najmuzzaman 
Date:  20141015 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 