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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int ll;

/*

8 3 7
3 -1 10 0 10 -1 1 -1
1 8
3 5
6 8
1 2
1 7
2 8
1 6


8 3 1
3 -1 10 0 10 -1 1 -1
2 8

*/

int n,k,q;
vector<int> a;
vector<ll> left_sum;
vector<ll> res;

ll calc_sum_at(int pos)
{
	int start=pos-k;
	ll sum=left_sum[pos]-(start>=0?left_sum[start]:0);
	sum=(sum>0?sum:0);
	return sum;
}

ll get_res(int l,int pos)
{
	if(pos<l+k-1)
		return 0;
	return res[pos];
}

void solve(int l,int r)
{
	if(r-l+1<k)
	{
		cout<<0<<endl;
		return;
	}

	int i=l+k-1;
	while(i<=r)
	{
		ll sum=calc_sum_at(i);
		res[i]=std::max(get_res(l,i-1),sum+get_res(l,i-k));
		++i;
	}
	cout<<res[r]<<endl;
}

int main()
{
	cin>>n>>k>>q;
	a.resize(n);
	for(int i=0;i<n;++i)
		cin>>a[i];
	left_sum.resize(n);
	left_sum[0]=a[0];
	for(int i=1;i<n;++i)
		left_sum[i]=a[i]+left_sum[i-1];
	res.resize(n);
	for(int i=0;i<q;++i)
	{
		int l,r;
		cin>>l>>r;
		--l;
		--r;
		solve(l,r);
	}

	return 0;
}