//Jakub Rozek
//Desant 2     //dla duzych k raczej popsute :(
//czas: min( q*k^2 q*logn*n/k)
//pamiec: 800*k^2 logn*n/k

#include "bits/stdc++.h"
using namespace std;

const int N=300005;//N=Q
const int RR=524288;//N=Q
const int K=40;
long long G,R;

struct str{
    long long l,r,id;
};

long long n,k,q,l,r,gr,grk,poc,kon;
long long sumpref[N];//
long long t[N];//
long long dpb[N];//
long long dp[800][K][K];
long long odp[N];
vector <str> pyt;
long long war[2][N][2];
long long tree[RR*2+2];

void solv(int a, int b)
{
    dpb[a-1]=0;
    dpb[b]=0;
    for(int i=a; i<=b; ++i)
    {
        if(i-k>=a) dpb[i]=max(dpb[i-1],t[i]+dpb[i-k]);
        else dpb[i]=max(dpb[i-1],t[i]);
    }
}

void solvmalek()
{
    poc=1;
    kon=G;
    gr=0;
    while(kon<=n)
    {
        for(int a=0; a<k; ++a)
        {
            solv(poc+a, kon);
            for(int b=0; b<k; ++b)
            {
                dp[gr][a][b]=dpb[kon-b];
            }
        }
        poc+=G;
        kon+=G;
        ++gr;
    }

    while(q--)
    {
        cin>>l>>r;
        r-=k-1;
        if(r-l<G+10)
        {
            solv(l,r);
            cout<<dpb[r]<<"\n";
            continue;
        }

        gr=(l-1)/G;
        poc=gr*G+1;
        kon=(gr+1)*G;
        grk=(r-1)/G;

        solv(l,kon);
        for(int i=0; i<k; ++i)
        {
            if(kon-i>=l) odp[i]=dpb[kon-i];
            else odp[i]=0;
        }

        ++gr;
        l=kon+1;
        while(gr<grk)
        {
            for(int i=0; i<k; ++i) dpb[l-1-i]=odp[i];
            for(int i=0; i<k; ++i) odp[i]=0;
            
            for(int a=0; a<k; ++a)
            {
                for(int b=0; b<k; ++b)
                {
                    odp[b]=max(odp[b], dpb[l+a-k]+dp[gr][a][b]);
                }
            }

            ++gr;
            l+=G;
        }
        
        for(int i=0; i<k; ++i) dpb[l-1-i]=odp[i];
        for(int i=l; i<=r; ++i) dpb[i]=max(dpb[i-1],t[i]+dpb[i-k]);
        
        cout<<dpb[r]<<"\n";
    }
}

long long query(int w, int a, int b, int c, int d)
{
    if(b<c || a>d) return 0;
    if(c<=a && b<=d) return tree[w];
    return max(query(w*2,a,(a+b)/2,c,d), query(w*2+1,(a+b)/2+1,b,c,d));
}

long long maks(int a, int b)
{
    long long wynik=0;
    if(a>=poc && a<=b && b<=kon) wynik=max(wynik,query(1,0,R-1,a,b));
    return wynik;
}

void solvduzek()
{
    for(int i=1; i<=q; ++i)
    {
        cin>>l>>r;
        r-=k-1;
        if(r-l<=30000)
        {
            solv(l,r);
            odp[i]=dpb[r];
            continue;
        }
        pyt.push_back({l,r,i});
    }

    poc=1;
    kon=k;
    while(poc<=n)
    {
        for(int i=0; i<k; ++i) tree[R+i]=t[poc+i];
        for(int i=R-1; i; --i) tree[i]=max(tree[i*2],tree[i*2+1]);
        for(int i=poc; i<=n; ++i)
        {
            war[0][i][0]=0;
            war[0][i][1]=i;
        }
        for(int i=poc; i<=kon; ++i) war[0][i][1]=kon+1;
        for(int i=1; i<=kon; ++i)
        {
            war[1][i][0]=0;
            war[1][i][1]=i;
        }
        for(int i=poc; i<=kon; ++i) war[1][i][1]=poc-1;
        for(int i=kon+1; i<=n; ++i)
        {
            if(war[0][i-1][0]==t[i]+war[0][i-k][0])
            {
                war[0][i][0]=war[0][i-1][0];
                war[0][i][1]=max(war[0][i-1][1],war[0][i-k][1]);
            }
            else if(war[0][i-1][0]>t[i]+war[0][i-k][0])
            {
                war[0][i][0]=war[0][i-1][0];
                war[0][i][1]=war[0][i-1][1];
            }
            else
            {
                war[0][i][0]=t[i]+war[0][i-k][0];
                war[0][i][1]=war[0][i-k][1];
            }
        }
        for(int i=poc-1; i>=1; --i)
        {
            if(war[1][i+1][0]==t[i]+war[1][i+k][0])
            {
                war[1][i][0]=war[1][i+1][0];
                war[1][i][1]=min(war[1][i+1][1],war[1][i+k][1]);
            }
            else if(war[1][i+1][0]>t[i]+war[1][i+k][0])
            {
                war[1][i][0]=war[1][i+1][0];
                war[1][i][1]=war[1][i+1][1];
            }
            else
            {
                war[1][i][0]=t[i]+war[1][i+k][0];
                war[1][i][1]=war[1][i+k][1];
            }
        }

        for(auto p:pyt)
        {
            if(p.r<poc || p.l>kon) continue;
            if(p.l<poc && kon<p.r)
            {
                odp[p.id]=max(odp[p.id], war[1][p.l][0]+war[0][p.r][0]+maks(war[1][p.l][1]+k,war[0][p.r][1]-k));
            }
            else if(poc<=p.l && p.r<=kon)
            {
                odp[p.id]=maks(p.l,p.r);
            }
            else if(poc<=p.l)
            {
                odp[p.id]=max(odp[p.id], war[0][p.r][0]+maks(p.l,war[0][p.r][1]-k));
            }
            else
            {
                odp[p.id]=max(odp[p.id], war[1][p.l][0]+maks(war[1][p.l][1]+k,p.r));
            }
        }
        poc+=k;
        kon+=k;
    }

    for(int i=1; i<=q; ++i) cout<<odp[i]<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k>>q;
    for(int i=1; i<=n; ++i)
    {
        cin>>sumpref[i];
        sumpref[i]+=sumpref[i-1];
    }
    n-=k-1;
    for(int i=1; i<=n; ++i)
    {
        t[i]=sumpref[i+k-1]-sumpref[i-1];
    }

    G=sqrt(n*k*k/2);
    R=1;
    while(R<k) R*=2;

    if(k<=K) solvmalek();
    else solvduzek();

    return 0;
}