COCI 2009/2010, Contest #5
Task PROGRAM
Mirko is trying to debug a piece of his code. First he creates an array of N integers and fills it with zeros. Then he repeatedly calls the following procedure (he is such a good coder he coded it in both C++ and Pascal):


As you can see, this procedure increases by one all elements in the array whose indices are divisible by jump.
Mirko calls the procedure exactly K times, using the sequence X_{1} X_{2} X_{3} ... X_{k} as arguments.
After this, Mirko has a list of Q special parts of the array he needs to check to verify that his code is working as it should be. Each of this parts is defined by two numbers, L and R (L ≤ R) the left and right bound of the special part. To check the code, Mirko must compute the sum of all elements of seq
between and including L and R. In other words seq
[L] + seq
[L+1] + seq
[L+2] + ... + seq
[R]. Since he needs to know the answer in advance in order to check it, he asked you to help him.
Input
The first line of input contains two integers, N (1 ≤ N ≤ 10^{6}), size of the array, and K (1 ≤ K ≤ 10^{6}), the number of calls to something
Mirko makes.
The second line contains K integers: X_{1} X_{2} X_{3} ... X_{k}, arguments passed to the procedure. (1 ≤ X_{i} < N).
The next line contains one integer Q (1 ≤ Q ≤ 10^{6}), number of special parts of the array Mirko needs to check.
The next Q lines contain two integers each L_{i} and R_{i} (0 ≤ L_{i} ≤ R_{i} < N), bounds of each special part.
Output
The output should contain exactly Q lines. The i^{th} line should contain the sum of elements seq
[L_{i}] + seq
[L_{i}+1] + seq
[L_{i}+2] + ... + seq
[R_{i}].
Sample Tests
Input10 4 1 1 2 1 3 0 9 2 6 7 7 Output35 18 3 
Input11 3 3 7 10 3 0 10 2 6 7 7 Output8 2 1 
Input1000000 6 12 3 21 436 2 19 2 12 16124 692 29021 Output16422 28874 
Sample 1 Description
The procedure is called with arguments 1, 1, 2, 1. After that the array contains values {4, 3, 4, 3, 4, 3, 4, 3, 4, 3}. The sum of indices 2 to 6 (inclusive) is 4 + 3 + 4 + 3 + 4 = 18.
Sample 2 Descrption
The array is {3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}.
All Submissions
Best Solutions
Point Value: 10 (partial)
Time Limit: 5.00s
Memory Limit: 32M
Added: Jul 13, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...