1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


struct odc{
        int a;
        int b;
        int indx;
};
    
bool acompare(odc l, odc p) { 
        if (l.a<p.a)
            return true;
        else if (l.a==p.a){
            return l.b>p.b;
        }else 
            return false;
}



int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n,k,q;
    cin>>n>>k>>q;

    int a,b;
    vector <ll> pref(n+1,0); //przerobić na globalną !! 
    vector <ll> dp(n+1,0);
    vector <odc> zap;
    vector <ll> wyn(q,0);

    //Wczytywanie sily i liczenie pref
    for (int i=1;i<=n;i++){
        cin>>a;
        pref[i]=pref[i-1]+a;
    }

    //Wczytwanie zapytan
    for (int j=0;j<q;j++){
        cin>>a>>b;
        zap.push_back({a,b,j});
    }

    //sortowanie zapytan po a,b
    sort(zap.begin(), zap.end(), acompare);
    // for (auto e:zap){
    //     cout<<e.a<<" "<<e.b<<" "<<e.indx<<endl;
    // }


    ll roz=0;
    // int kon=0,pocz=0;
    // odc o;
    int poprz_a=0;
    int poprz_b=0;
    int ind;
    for (int j=0;j<q;j++){
        auto [a,b,ind]=zap[j];

        if(b-a<k-1){
            // wyn[zap[j].indx]=0;
            //nie trzeba bo 0 juz sa
            continue;
        }
        //nie tezeba liczyć jeśli pocz prze taki sam
        if (a!=poprz_a){
            //zerowanie od a-1,a+k-1
            // cout<<(a-1)<<" "<<b-k<<" "<<a+k-1<<endl;
            // fill(dp.begin() + (a-1),dp.begin()+b-k, 0);
            // pocz=max(a-1,kon);
            // kon=min(a+k-1,b-k);
            // cout<<"Zerowanie od "<<a-1<<" do "<<kon<<endl;
            // for (int p=pocz;p<=kon;p++){
            //     dp[p]=0;
            //     // cout<<"zeruje"<<p<<endl;
            // }
            dp[a+k-1-1]=0;
            for (int i=a+k-1;i<=b;i++){
                roz=pref[i]-pref[i-k];
                if (i-k<(a+k-1)){
                    dp[i]=max(roz,dp[i-1]);
                }
                else
                    dp[i]=max(dp[i-k]+roz,dp[i-1]);
            }
        }

        wyn[zap[j].indx]=dp[b];
        poprz_a=a;
        poprz_b=b;
    }

    for (auto e:wyn){
        cout<<e<<"\n";
    }
    
    

    return 0;
}