#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC target("avx2")
#pragma GCC optimization("Ofast")
#pragma GCC optimization("unroll-loops")
*/

using namespace __gnu_pbds;
using namespace std;

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define vt vector
#define maxi(x,y) x=max(x,y)
#define mini(x,y) x=min(x,y)
#define size(x) (int)x.size()
#define all(r) begin(r),end(r)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cx real()
#define cy imag()
#define precision(x) setprecision(x)<<fixed
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#ifndef DEBUG
#define DEBUG false
#endif
#define dbg if(DEBUG)

typedef long long ll;
typedef long double ld;
typedef complex<long double> cplx;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef vt<int> vi;
typedef vt<vi> vvi;
typedef vt<bool> vb;
typedef vt<vb> vvb;
typedef vt<char> vc;
typedef vt<vc> vvc;
typedef vt<string> vs;
typedef vt<vs> vvs;
typedef vt<ll> vll;
typedef vt<vll> vvll;
typedef vt<ld> vld;
typedef vt<vld> vvld;
typedef vt<cplx> vcplx;
typedef vt<vcplx> vvcplx;

template<typename T>
using ordset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T1,typename T2>
ostream& operator<<(ostream &os,pair<T1,T2>& VAR){
	os<<"("<<VAR.e1<<","<<VAR.e2<<")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os,vt<T>& VAR){
	os<<"[";
	for(int i=0;i<size(VAR)-1;i++)
		os<<VAR[i]<<",";
	if(size(VAR))
		os<<VAR.back();
	os<<"]";
	return os;
}

template<typename T>
istream& operator>>(istream& is,complex<T>& VAR){
	T value;
	is>>value;
	VAR.real(value);
	is>>value;
	VAR.imag(value);
	return is;
}

const bool TESTS=false;

const int MAXN=3e5+10;

ll qans[MAXN];
ll a[MAXN];
pair<int,int> query[MAXN];
int n,k,q;

ll dpl[MAXN];
ll dpr[MAXN];

void solve_smallk(int l,int r,vi ids){
	if(l==r){
		if(k==1){
			for(auto& x:ids)
				if(a[l]>0)
					qans[x]=a[l];
		}
		return;
	}
	int mid=(l+r)/2;
	dpl[mid+1]=0;
	for(int i=mid;i>=l;i--){
		dpl[i]=dpl[i+1];
		if(i+k<=mid+1&&dpl[i]<dpl[i+k]+a[i+k-1])
			dpl[i]=dpl[i+k]+a[i+k-1];
	}
	dpr[mid]=0;
	for(int i=mid+1;i<=r;i++){
		dpr[i]=dpr[i-1];
		if(i-k>=mid&&dpr[i]<dpr[i-k]+a[i])
			dpr[i]=dpr[i-k]+a[i];
	}
	vi lewo,prawo,akt;
	for(auto& x:ids){
		if(query[x].e1>mid)
			prawo.eb(x);
		else
		if(query[x].e2<=mid)
			lewo.eb(x);
		else{
			qans[x]=dpl[query[x].e1]+dpr[query[x].e2];
			akt.eb(x);
		}
	}
	for(int len=1;len<k;len++){
		int lenl=len;
		int lenr=k-len;
		if(mid-lenl+1<l)
			continue;
		if(mid+1+lenr-1>r)
			continue;
		ll def=a[mid+lenr];
		dpl[mid+1]=0;
		for(int i=mid;i>=l;i--){
			dpl[i]=dpl[i+1];
			if(i+k+lenl<=mid+1&&dpl[i]<dpl[i+k]+a[i+k-1])
				dpl[i]=dpl[i+k]+a[i+k-1];
		}
		dpr[mid]=0;
		for(int i=mid+1;i<=r;i++){
			dpr[i]=dpr[i-1];
			if(i-k-lenr>=mid&&dpr[i]<dpr[i-k]+a[i])
				dpr[i]=dpr[i-k]+a[i];
		}
		for(auto& x:akt)
			if(query[x].e1<=mid-lenl+1&&query[x].e2>=mid+lenr)
				maxi(qans[x],dpl[query[x].e1]+dpr[query[x].e2]+def);
	}
	solve_smallk(l,mid,lewo);
	solve_smallk(mid+1,r,prawo);
}

vi qidl[MAXN];
vi qidr[MAXN];
int farl[MAXN];
int farr[MAXN];

ll dp[MAXN];

bitset<MAXN> solved;

int val[MAXN];

void solve_bigk(){
	for(int i=0;i<q;i++){
		qidl[query[i].e1].eb(i);
		if(query[i].e2>farl[query[i].e1])
			farl[query[i].e1]=query[i].e2;
	}
	for(int i=1;i<=n;i++){
		if(size(qidl[i])<=1){
			if(i+k-1<=n)
				dp[i+k-1]=0ll;
			continue;
		}
		for(int j=i+k-1;j<=farl[i];j++){
			dp[j]=a[j]+dp[j-k];
			if(dp[j-1]>dp[j])
				dp[j]=dp[j-1];
		}
		for(auto& id:qidl[i]){
			qans[id]=dp[query[id].e2];
			solved[id]=true;
		}
		if(i+k-1<=n)
			dp[i+k-1]=0ll;
	}
	for(int i=n;i>=1;i--){
		farr[i]=n+1;
		a[i]=a[i+1]+val[i];
		if(i+k<=n)
			a[i]-=val[i+k];
	}
	for(int i=0;i<q;i++){
		if(solved[i])
			continue;
		qidr[query[i].e2].eb(i);
		if(query[i].e1<farr[query[i].e2])
			farr[query[i].e2]=query[i].e1;
	}
	dp[n+1]=0;
	for(int i=n;i>=1;i--){
		for(int j=i-k+1;j>=farr[i];j--){
			dp[j]=a[j]+dp[j+k];
			if(dp[j+1]>dp[j])
				dp[j]=dp[j+1];
		}
		for(auto& id:qidr[i])
			qans[id]=dp[query[id].e1];
		if(i-k+1>=1)
			dp[i-k+1]=0ll;
	}
}

void solve(){
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++){
		cin>>val[i];
		a[i]=a[i-1]+val[i];
		if(i>=k)
			a[i]-=val[i-k];
	}
	for(int i=0;i<q;i++)
		cin>>query[i].e1>>query[i].e2;
	if(k<=40){
		vi ids(q);
		iota(all(ids),0);
		solve_smallk(1,n,ids);
	}
	else
		solve_bigk();
	for(int i=0;i<q;i++)
		cout<<qans[i]<<'\n';
}

int32_t main(){
	fastio;
	if(TESTS){
		int TEST_COUNT;
		cin>>TEST_COUNT;
		for(int i=0;i<TEST_COUNT;i++)
			solve();
	}
	else
		solve();
	return 0;
}