#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 100005
#define inf 0x3f3f3f3f3f3f3f3f

int n,m,Q,a[maxn],b[maxn],to[maxn],aa[maxn];
ll f[maxn],g[maxn],res[maxn],tmp[maxn];
struct qry{int l,r,id;};
typedef vector<qry>vec;

void F(int l,int r,int m)
{
	ll mx=0;
	f[l]=a[l];
	if(l<=r){
		For(i,l+1,r){
			if(i-m>=l)mx=max(mx,f[i-m]);
			f[i]=max(f[i-1],a[i]+mx);
			mx=max(mx,f[i-1]-a[i]);
		}
	}else{
		Rep(i,l-1,r){
			if(i+m<=l)mx=max(mx,f[i+m]);
			f[i]=max(f[i+1],a[i]+mx);
			mx=max(mx,f[i+1]-a[i]);
		}
	}
}
void G(int l,int r,int m)
{
	g[l]=0;
	ll mx=-a[l];
	if(l<=r){
		For(i,l+1,r){
			if(i-m>=l)mx=max(mx,g[i-m]);
			g[i]=max(g[i-1],a[i]+mx);
			mx=max(mx,g[i-1]-a[i]);
		}
	}else{
		Rep(i,l-1,r){
			if(i+m<=l)mx=max(mx,g[i+m]);
			g[i]=max(g[i+1],a[i]+mx);
			mx=max(mx,g[i+1]-a[i]);
		}
	}
}

void work1(int l,int r,vec o)
{
	tmp[l-1]=0;
	For(i,l,r)tmp[i]=tmp[i-1]+a[i];
	for(auto t:o)res[t.id]=max(res[t.id],tmp[t.r]-tmp[t.l-1]);
}

void solve2(int l,int r,int m,vec o)
{
	if(!o.size())return;
	int n=r-l+1;
	if(m==1)return work1(l,r,o);
	int m2=m/2;
	vec o1,o2,o3;
	int p=l;
	For(i,1,n)
		if((i-1)%m<m2)to[i+l-1]=p,b[p]=i+l-1,++p;
	int p2=p;
	For(i,1,n)
		if((i-1)%m>=m2)to[i+l-1]=p,b[p]=i+l-1,++p;
	for(auto x:o){
		int ql=x.l-l,qr=x.r-l;
		if(ql%m<m2&&qr%m<m2)o1.pb((qry){to[x.l],to[x.r],x.id});
		else if(ql%m>=m2&&qr%m>=m2)o2.pb((qry){to[x.l],to[x.r],x.id});
		else o3.pb(x);
	}
	For(i,1,(n+m-m2-1)/m+1){
		int pos=min(n,(i-1)*m+m2)+l-1;
		F(pos+1,r,m);
		G(pos,l,m);
		for(auto x:o3)
			if(x.l<=pos&&x.r>=pos+1)res[x.id]=max(res[x.id],g[x.l]+f[x.r]);
		F(pos,l,m);
		G(pos+1,r,m);
		for(auto x:o3)
			if(x.l<=pos&&x.r>=pos+1)res[x.id]=max(res[x.id],f[x.l]+g[x.r]);
	}
	For(i,l,r)aa[i]=a[b[i]];
	For(i,l,r)a[i]=aa[i];
	solve2(l,p2-1,m2,o1);
	solve2(p2,r,m-m2,o2);
}

void solve(int l,int r,vec o)
{
	if(!o.size())return;
	int n=r-l+1;
	if(m==1)return work1(l,r,o);
	if(0.5*m*m>=n){
		For(i,1,(n-1)/m+1){
			int pos=min(i*m,n)+l-1;
			F(pos+1,r,m);
			G(pos,l,m);
			for(auto x:o)
				if(x.l<=pos&&x.r>=pos+1)res[x.id]=max(res[x.id],g[x.l]+f[x.r]);
			F(pos,l,m);
			G(pos+1,r,m);
			for(auto x:o)
				if(x.l<=pos&&x.r>=pos+1)res[x.id]=max(res[x.id],f[x.l]+g[x.r]);
		}
		solve2(l,r,m,o);
		return; 
	}
	int mid=l+r>>1;
	vec o1,o2;
	for(auto x:o){
		if(x.r<mid)o1.pb(x);
		else if(x.l>mid)o2.pb(x);
	}
	int tl=max(l,mid-m+1);
	int tr=min(r,mid+m-1);
	For(i,tl,tr){
		G(i,l,m);
		G(i,r,m);
		for(auto t:o)
			if(t.l<=i&&t.r>=i)res[t.id]=max(res[t.id],g[t.l]+g[t.r]+a[i]);
	}
	solve(l,mid,o1);
	solve(mid+1,r,o2);
}

signed main()
{
	n=read(),m=read(),Q=read();
	For(i,1,n)a[i]=read();
	vector<qry>o;
	For(i,1,Q){
		int l=read(),r=read();
		if(l==r)res[i]=a[l];
		else o.pb((qry){l,r,i});
	}
	solve(1,n,o);
	For(i,1,Q)printf("%lld\n",res[i]);
	return 0;
}