TOI17: Sequel

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n, Q;
    scanf("%d %d", &n, &Q);

    int ar[n + 1];
    for(int i=1;i<=n;i++) scanf("%d", &ar[i]);

    int sqrtn = sqrt(n);
    int dp[sqrtn + 1][n + 1];
    for(int i=1;i<=sqrtn;i++){
        for(int j=1;j<=n;j++){
            dp[i][j] = dp[i][max(j - i, 0)] + ar[j];
        }
    }

    for(int q=1;q<=Q;q++){
        int l, r, m;
        scanf("%d %d %d", &l, &m, &r);
        int ans = 0;
        if(m < sqrtn)
            ans = dp[m][l + m * ((r - l) / m)] - dp[m][l] + ar[l];
        else{
            for(int i=l;i<=r;i+=m) ans += ar[i];
        }
        printf("%d ", ans);
    }

    return 0;
}