SP26954 KALTSUM - k Alternating Sum

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?

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.

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.**