Problem: You are given an array of N integers A[1] , A[2] , ... , A[N] . You have to answer Q queries. Each query consists of 3 integers L, R and K. For each query, you have to find the value of the Skipping Sum in the following manner :

       def skipping_sum(L,R,K) :
              sum = 0
              while L ≤ R :
                    sum = sum + A[L]
                    L = L + K 
              return sum
Input
The first line consists of 2 space separated integers N and Q. The next line consists of N space separated integers, the i^th integer being A[i]. Then, Q lines follow, each line consisting of 3 space separated integers L, R and K.
Output
Print the answer to each query on a new line.
Constraints
1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
0 ≤ A[i] ≤ 10^5
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ 10  

NOTE:
We are using 1-based indexing for array A. 

SAMPLE INPUT
8 6
5 4 2 1 7 9 10 9
1 8 1
1 8 2
4 8 9
3 7 2
3 7 3
3 7 4

SAMPLE OUTPUT
47
24
1
19
11
12

Explanation

For query 1 : A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[8] = 47
For query 2 : A[1] + A[3] + A[5] + A[7] = 24
For query 3 : A[4] = 1
For query 4 : A[3] + A[5] + A[7] = 19
For query 5 : A[3] + A[6] = 11
For query 6 : A[3] + A[7] = 12

Solution (in PYTHON):

Solution:
import math
n,q=(int(e) for e in raw_input().split())
arr=[int(e) for e in raw_input().split()]

dp=[0]*len(arr)
dp2=[0]*len(arr)
dp3=[0]*len(arr)

for i in xrange(len(arr)-1,-1,-1):
	dp[i]=[arr[i]]*11
	for j in xrange(1,11):
		if (i+j) < len(arr):
			dp[i][j]+=dp[i+j][j]

for e in xrange(q):
	l,r,k=(int(e) for e in raw_input().split())
	l,r=l-1,r-1
	n=int(math.ceil((r-l)/k)*k+l)
	#print n
	print dp[l][k]-dp[n][k]+arr[n]