## KALTSUM - k Alternating Sum

no tags

Sameen has:

1. An array having N integers
2. 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 j-th number…

(j-i+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

(j-i+1) will be divisible by k.

### Example

```Input:
6 64 1 -2 -3 4 52 5 21 6 11 6 31 6 63 3 13 4 1```
```Output:
-23-39-21```
`Explanation:In the first query, the subarray is [ 1, -2, -3, 4].So “2 alternating sum” is equal to: [1-2]-[-3+4] = -2For the second query, we get -+[-2]-[-3]+- = 3N.B: Dataset is huge. Use faster I/O method. ` Tanmoy Tapos Datta: 2019-04-03 10:47:53 Perfect example for heavy light trick. smtcoder: 2016-10-26 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: 2016-10-04 17:39:01 O((r-l+1)*q) is TLE ? I am definitely missing something obvious.. :/ Reply: You need to do better. Last edit: 2016-12-30 01:16:09 Rishav Goyal: 2016-08-14 16:03:43 easy ..... just one trick. < 1 minute solution Last edit: 2016-08-14 16:04:00 fly_sky12: 2016-05-23 13:15:26 getting TLE :( how to overcome it ??