NAJ0001 - Divisible Number Sum

no tags 

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 number and query answer.

Write a blank line between two cases.

Sample

Input
2
5 2
1 2 3 4 6
2 1 5
5 1 4
5 2
2 3 5 3 7
3 2 4
5 1 5

Output
Case #1
12
0

Case #2
6
5

Hints:

Query 1: in array index 1 to 5 the set S is {2, 4, 6} because those are fully divisible by 2, so the 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 the sum is 0.

Data set is so huge. Use faster I/O


hide comments
[Lakshman]: 2015-04-20 13:59:14

AC nice one.

Last edit: 2015-04-20 16:40:05
mjh: 2014-12-15 08:59:08

any hint for tle?

(Tjandra Satria Gunawan)(曾毅昆): 2014-11-06 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.
--ans(Francky)--> It is a known thing ; also appears with pyramid.

Last edit: 2014-11-06 20:32:15

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