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
109
110
111
112
#include <iostream>
#include <cmath>
#include <algorithm>

#include <vector>


using namespace std;

struct przedzial{
	int l,r;
	int i;
};

long long wyniki[300002];
int cmp(const przedzial & a, const przedzial & b) {
	auto x = -(a.l-b.l);
	if (x == 0) return (a.r < b.r);
	return (a.l<b.l);;
}

long long maxium[300002];
long long kolejnek[300002];
long zolnierze[300002];
przedzial liri[300002];

void printliri();

long long n,k,ktemp=0,licznik=1;
int q;
int main(){
	

	cin>>n>>k>>q;
	for(long i=1;i<=n;i++) {
		cin>>zolnierze[i];
	//	zolnierze[i]=sprintf("%d" );
//		cout<<"i" << i << "zol " << zolnierze[i];
	}
//	cout <<endl;
	for(long i=1;i<=q;i++)	{
		cin>>liri[i].l >> liri[i].r;

		liri[i].i=i;
	}
	for(long i=1;i<=k;i++) {
		ktemp+=zolnierze[i];
	}
//	cout <<endl<< ktemp <<endl;
	kolejnek[k]=ktemp;
	for(long i=k+1;i<=n;i++) {
		ktemp += -zolnierze[i-k] + zolnierze[i];
		kolejnek[i]=ktemp;
	}
	// for(long i=k;i<=n;i++) {
	// 	cout<<kolejnek[i]<< " ";
	// }
//	cout <<endl;
///	printliri();
	sort(liri+1, liri+q+1, cmp);
//	cout<<endl;
//	printliri();

	for(long w=1;w<=q;w++){
		for(long i=0;i<=n;i++) {
//			cout<<maxium[i] << " " ;
			maxium[i]=0;
		}
//		cout << w<<" i"<<liri[w].i<<endl;

		long l=liri[w].l,r=liri[w].r;

		if(r-l+1<k or r<k or n-l+1<k) {
			wyniki[liri[w].i]=0 ;
//			cout <<"tenwarunek" <<endl;
			continue;
			
		}
		//if(l<k)

		maxium[k+l-1]=kolejnek[k+l-1];
		for(int i=k+l-1;i<=n;i++) {
			//long long = temp 
			if(maxium[i-1]>maxium[i-k]+kolejnek[i])
				maxium[i] = maxium[i-1];
			else
				maxium[i] = maxium[i-k]+kolejnek[i];

//			maxium[i]=max(maxium[i-1],maxium[i-k]+kolejnek[i]);
			if(i==r) {
				wyniki[liri[w].i]=maxium[i] ;
				if(liri[w+1].l==l) {
					w++;
					if(r==liri[w].r) i--;
					r=liri[w].r;
				}
				else break;
			}
		}
	}
	for(long w=1;w<=q;w++){
		cout<<wyniki[w]<<endl;
	}


	return 0;
}	
void printliri() {
	for(long i=1;i<=q;i++)	{
		cout<< "l r i = " <<liri[i].l << " " <<liri[i].r << " " <<liri[i].i<<endl;
	}
}