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:
(N, Q) = map(int,str(raw_input()).split())
nums = map(int,str(raw_input()).split())

sums = []

for K in range(1,min(N,11)):
	#print "first loop:", K
	sums_K = []
	for I in range(N):
		#print "second loop:", I
		if I < K:
			sums_K.append(nums[I])
		else:
			sums_K.append(sums_K[I-K] + nums[I])
	sums.append(sums_K)

"""
for I in range(len(sums)):
	print " ".join(map(str,sums[I]))
"""

for I in range(Q):
	(L, R, K) = map(int,str(raw_input()).split())
	L -= 1
	R -= 1
	if K >= N:
		print nums[L]
	else:
		rem = (R-L) % K
		print sums[K-1][R-rem] - sums[K-1][L] + nums[L]