KALTSUM  k Alternating Sum
Sameen has:
 An array having N integers
 Q friends
His friends are curious about the array. So, each of his friends asks Sameen a question about the array. Every question is described by 3 integers: i, j and k. In reply to a question, Sameen has to say the “k alternating sum” of the subarray starting at position i and ending at position j [1 based indexing]
“k alternating sum” of a subarray starting at position i and ending at position j can be calculated in the following way:
Add the first k numbers[starting from position i]
Subtract the second k numbers[starting from position i+k]
Add the third k numbers[starting from position i+2*k]
Subtract the fourth k numbers[starting from position i+3*k]
And so on till adding/subtracting the jth number…
(ji+1) will be divisible by k.
[See sample Input/output and explanation section for more details]
Can you help Sameen in answering the questions?
Input
The first line of input contains two integers N and Q. The next line contains N integers, the numbers in the array. Then each of the following Q lines contains 3 integers i, j & k.
Output
For each query output an integer in a separate line, the answer for that query. Queries should be answered in the order given in the input.
Constraints:
1 ≤ k ≤ 100000
1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1000000000 ≤ Value of a number in the array ≤ 1000000000
(ji+1) will be divisible by k.
Example
Input:6 6
4 1 2 3 4 5
2 5 2
1 6 1
1 6 3
1 6 6
3 3 1
3 4 1
Output:2
3
3
9
2
1
Explanation:
In the first query, the subarray is [ 1, 2, 3, 4].
So “2 alternating sum” is equal to: [12][3+4] = 2
For the second query, we get [4][1]+[2][3]+[4][5] = 3
N.B: Dataset is huge. Use faster I/O method.
hide comments
smtcoder:
20161026 21:52:25
This is one badass problem!..just think of the kind of time complexity ur program needs in order to avoid TLEs..and after that think of how you can implement the code of that time complexity.. U will definitely find some way.. 

dwij28:
20161004 17:39:01
O((rl+1)*q) is TLE ? I am definitely missing something obvious.. :/


Rishav Goyal:
20160814 16:03:43
easy ..... just one trick. < 1 minute solution Last edit: 20160814 16:04:00 

fly_sky12:
20160523 13:15:26
getting TLE :(

Added by:  Bertho Coder 
Date:  20160427 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  National High School Programming Contest 2016 