skipping-sum-1

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

Source: hackerearth | Difficulty: EASY


Solutions:
line1=input();
z= [int(l) for l in line1.split()]
num=z[0]
testcases=z[1]
input_numbers=input();
arr= [int(l) for l in input_numbers.split()]
backup=[];
for i in range(1,11):
	dist=[];
	dist.append(0);
	for j in range(0,num):
		if j<=i-1:
			dist.append(arr[j]);
		else:
			temp=arr[j]+dist[j-i+1];
			dist.append(temp);
	backup.append(dist);	

while testcases>0:
	query=input();
	temp= [int(l) for l in query.split()];
	(start,end,gap)=(temp[0],temp[1],temp[2]);
	finalIndex=end - (end-start)%gap;
	print(backup[gap-1][finalIndex]-backup[gap-1][start]+arr[start-1]);
	testcases=testcases-1;


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

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

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

for e in range(q):
	l,r,k=(int(e) for e in 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])