Expert.
Put your skills to the test.

Problem summary

Insert array elements into a multiset one by one. After each insertion, sum the elements at one-based sorted positions 1,k+1,2k+1,... .

Constraints

1 ≤ n ≤ 100000; 1 ≤ k ≤ n; |a[i]| ≤ 1000000000.

Worked example

Official statement example.

6 3
5 6 1 1 4 7

5
5
1
7
6
6

Solution analysis

1. Sort all future occurrences by (value,input index), assigning each a unique rank. Partition this fixed order into blocks of about √n positions. Each block stores its currently active values in sorted order, so inserting one occurrence changes only one block of at most √n elements.
2. For k≤block size, rebuild the changed block’s sums by local index modulo k. During an answer scan, if s elements precede a block, its selected local indices are congruent to −s modulo k. Add that residue sum and advance s by the active count. If k is larger than the block size, a block has at most one selected element and direct indexing suffices.
3. In the sample after the fourth insertion the multiset is [1,1,5,6]. Its zero-based selected indices are 0 and 3, so the answer is 1+6=7. Negative values and duplicate occurrences require no special arithmetic rule.

Why it works

The fixed block ordering agrees with the global sorted order of all active occurrences. A local index j is selected exactly when (s+j) mod k=0, so each scanned block contributes precisely its selected elements. The residue table or single-element case computes that same sum. Updating only the affected block preserves this invariant after every insertion.

Watch out. Positions are 1,k+1,..., corresponding to index 0 modulo k. Use 64-bit sums and distinguish duplicate occurrences when assigning ranks.

An independently written complete program with standard headers.

// Key idea: The fixed block ordering agrees with the global sorted order of all active occurrences. A
// local index j is selected exactly when (s+j) mod k=0, so each scanned block contributes precisely
// its selected elements.
#include<algorithm>
#include<cmath>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<long long>a(n);
    vector<pair<long long,int>>sorted;
    for(int i=0;i<n;++i){
        cin>>a[i];
        sorted.push_back({a[i],i});
    }
    sort(sorted.begin(),sorted.end());
    int blockSize=max(1,static_cast<int>(sqrt(n))+1);
    int blocks=(n+blockSize-1)/blockSize;
    vector<int>owner(n);
    for(int rank=0;rank<n;++rank){
        owner[sorted[rank].second]=rank/blockSize;
    }
    vector<vector<long long>>active(blocks);
    vector<vector<long long>>sums(blocks,vector<long long>(min(k,blockSize)));
    for(int i=0;i<n;++i){
        int b=owner[i];
        auto&values=active[b];
        values.insert(lower_bound(values.begin(),values.end(),a[i]),a[i]);
        if(k<=blockSize){
            fill(sums[b].begin(),sums[b].end(),0);
            for(int j=0;j<static_cast<int>(values.size());++j){
                sums[b][j%k]+=values[j];
            }
        }
        int offset=0;
        long long answer=0;
        for(int j=0;j<blocks;++j){
            int residue=(k-offset)%k;
            if(k<=blockSize){
                answer+=sums[j][residue];
            }
            else if(residue<static_cast<int>(active[j].size())){
                answer+=active[j][residue];
            }
            offset=(offset+static_cast<int>(active[j].size()))%k;
        }
        cout<<answer<<'\n';
    }
}