I tried to solve this problem but failed. Would anyone please help me to solve this problem

Problem Statement:

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.

Sample 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

Sample Output:

-2

3

-3

9

-2

1