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 [4]-[1]+[-2]-[-3]+[4]-[5] = 3N.B: Dataset is huge. Use faster I/O method. `