#include <bits/stdc++.h>

#define _2137 0
#define pb push_back
#define ff first
#define ss second

#define cap 1000000

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;



using namespace std;
//10^6

struct bignum{
    ll n18,n12,n6;
    bool sign;
};

bignum nums[300001];
/*
void swaP(bignum *num1,bignum *num2){
    bignum temp = *num1;
    *num1 = *num2;
    *num2 = temp;

}
*/

bignum reverse(bignum num){
    bignum temp;
    if(num.sign) return temp={-num.n18,-num.n12,-num.n6,false};
    else   return temp={-num.n18,-num.n12,-num.n6,true};
}

void debugout(bignum num){
    cout<<num.n18<<" "<<num.n12<<" "<<num.n6<<" "<<num.sign<<endl;
}



bool islarger(bignum num,bignum val){

    if(abs(num.n18)!=abs(val.n18)){
        if(abs(num.n18)>abs(val.n18)){
            return true;
        }
        else return false;
    }
    else if(abs(num.n12)!=abs(val.n12)){
        if(abs(num.n12)>abs(val.n12)){
            return true;
        }
        else return false;
    }
    else if(abs(num.n6)!=abs(val.n6)){
        if(abs(num.n6)>abs(val.n6)){
            return true;
        }
        else return false;
    }
    else return true;

}

bool compare(bignum num,bignum val){

    if(num.n18!=val.n18){
        if(num.n18>val.n18) return true;
        else return false;
    }
    else if(num.n12!=val.n12){
        if(num.n12>val.n12) return true;
        else return false;
    }
    else if(num.n6!=val.n6){
        if(num.n6>val.n6) return true;
        else return false;
    }
    else return true;

}



bignum add(bignum num,bignum val){
    
    if(num.sign){
        
        if(val.sign){
            
            num.n18+=val.n18; num.n12+=val.n12; num.n6+=val.n6;
            short diff12=num.n12/cap , diff6=num.n6/cap;
            num.n6=num.n6%cap; num.n12=num.n12%cap; num.n12+=diff6; num.n18+=diff12;
            return num;
        }
        else{
            
            bool check = islarger(num,val);
            //cout<<islarger(num,val)<<endl;
            num.n18+=val.n18; num.n12+=val.n12; num.n6+=val.n6;

            if(check){
                
                short diff12=abs(num.n12)/cap , diff6=abs(num.n6)/cap;
                if(num.n6<0)    { num.n6=cap-abs(num.n6)%cap; num.n12-=diff6+1;
                }
                else            { num.n6=num.n6%cap; num.n12+=diff6;
                }
                if(num.n12<0)   { num.n12=cap-abs(num.n12)%cap; num.n18-=diff12+1;
                }
                else            { num.n12=num.n12%cap; num.n18+=diff12;
                }
                return num;
            }   
            else{
                short diff12=abs(num.n12)/cap , diff6=abs(num.n6)/cap;
                
                if(num.n6>0)    { num.n6=num.n6%cap-cap; num.n12+=diff6+1;
                }
                else            { num.n6=-abs(num.n6)%cap; num.n12-=diff6;
                }
                if(num.n12>0)   { num.n12=num.n12%cap-cap; num.n18+=diff12+1;
                }
                else            { num.n12=-abs(num.n12)%cap; num.n18-=diff12;
                }
                if(num.sign) num.sign=false;
                else num.sign=true;
                return num;
            }
        }
    }
    else{
        if(val.sign){
            swap(num,val);
            bool check = islarger(num,val);
            num.n18+=val.n18; num.n12+=val.n12; num.n6+=val.n6;
            if(check){
                short diff12=abs(num.n12)/cap , diff6=abs(num.n6)/cap;
                if(num.n6<0)    { num.n6=cap-abs(num.n6)%cap; num.n12-=diff6+1;
                }
                else            { num.n6=num.n6%cap; num.n12+=diff6;
                }
                if(num.n12<0)   { num.n12=cap-abs(num.n12)%cap; num.n18-=diff12+1;
                }
                else            { num.n12=num.n12%cap; num.n18+=diff12;
                }
                return num;
            }   
            else{
                short diff12=abs(num.n12)/cap , diff6=abs(num.n6)/cap;
                if(num.n6>0)    { num.n6=num.n6%cap-cap; num.n12+=diff6+1;
                }
                else            { num.n6=-abs(num.n6)%cap; num.n12-=diff6;
                }
                if(num.n12>0)   { num.n12=num.n12%cap-cap; num.n18+=diff12+1;
                }
                else            { num.n12=-abs(num.n12)%cap; num.n18-=diff12;
                }
                if(num.sign) num.sign=false;
                else num.sign=true;
                return num;
            }
            
        }
        else{
            num.n18+=val.n18; num.n12+=val.n12; num.n6+=val.n6;
            short diff12=abs(num.n12)/cap , diff6=abs(num.n6)/cap;
            num.n6=-abs(num.n6)%cap; num.n12=-abs(num.n12)%cap;
            num.n12-=diff6; num.n18-=diff12;
            return num;   
        }
    }
}

bignum mx={0,0,0,true};

uint n,k,q;

void graph(int beg,int end,bignum temp){
    bignum temp2;
    if(compare(temp,mx)) mx=temp;
    for(int i=beg+k;i<=end;++i){
        temp2=add(temp,nums[i]);
        //debugout(temp2);
        graph(i,end,temp2);
    }

}




int main() {
    
    bignum input,go={0,0,0,true};
    
    //bignum test1={0,0,9,true},test2={0,0,10,true};

    //debugout(add(test1,reverse(test2)));
    
    long long in,in6,in12,in18;
    scanf("%d %d %d",&n,&k,&q);
    
    scanf("%Ld",&in);
    
    bignum prev[n];

    if(in>=0){ in6=in%cap; in/=cap; in12=in%cap; in/=cap; in18=in; input={in18,in12,in6,true}; }
    else{ in6=-abs(in)%cap; in/=cap; in12=-abs(in)%cap; in/=cap; in18=-abs(in); input={in18,in12,in6,false}; }
    go=add(go,input);
    prev[0]=input;

    for(int i=1;i<k;++i){
        scanf("%Ld",&in);
        if(in>=0){ in6=in%cap; in/=cap; in12=in%cap; in/=cap; in18=in; input={in18,in12,in6,true}; }
        else{ in6=-abs(in)%cap; in/=cap; in12=-abs(in)%cap; in/=cap; in18=-abs(in); input={in18,in12,in6,false}; }
        prev[i]=input;
        go=add(go,input);
    }

    nums[1]=go;
    //debugout(go);
    for(int i=k;i<n;++i){
        go=add(go,reverse(prev[i-k]));
        scanf("%Ld",&in);
        if(in>=0){ in6=in%cap; in/=cap; in12=in%cap; in/=cap; in18=in; input={in18,in12,in6,true}; }
        else{ in6=-abs(in)%cap; in/=cap; in12=-abs(in)%cap; in/=cap; in18=-abs(in); input={in18,in12,in6,false}; }
        //cout<<"IN  "; debugout(input);
        prev[i]=input;
        go=add(go,input);
        nums[i-k+2]=go;
        //debugout(go);
    }



    vector <bignum> ans;

    for(int i=0,a,b;i<q;++i){
        scanf("%d %d",&a,&b);
        int end=b-k+1;
        if(b-a+1>=k){
            mx={0,0,0,true};
            for(int j=a;j<=end;++j){
        
                for(int l=j;l<=end;l+=k){

                    graph(l,end,nums[l]);
                }
                


            }
            
            ans.pb(mx);

        }
        else ans.pb({0,0,0,true});
        

    }
    //ans.pb({1,10,1000,true});
    for(int i=0;i<q;++i){
        int temp1=5,temp2=5,temp3,temp4;
        if(ans[i].n18!=0) {
            printf("%Ld",ans[i].n18);
            temp3=ans[i].n12;
            temp4=ans[i].n6;
            while(temp3!=0){
                temp3/=10;
                --temp1;
            }
            while(temp4!=0){
                temp4/=10;
                --temp2;
            }
            while(temp1>0){
                printf("0");
                --temp1;
            }
            cout<<ans[i].n12;
            while(temp2>0){
               printf("0");
                --temp2;
            }
            printf("%Ld\n",ans[i].n6);
        }
        else if(ans[i].n12!=0){
            printf("%Ld",ans[i].n12);
            temp4=ans[i].n6;
            while(temp4!=0){
                temp4/=10;
                --temp2;
            }
            cout<<ans[i].n12;
            while(temp2>0){
                printf("0");
                --temp2;
            }
            printf("%Ld\n",ans[i].n6);
        }
        else printf("%Ld\n",ans[i].n6);

    }


	 return _2137;
}