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
#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#pragma GCC optimize ("Ofast")
using namespace std;
const int MXN=3e5+10;
long long s[MXN], dp[MXN], odp[MXN];
int a[MXN];
int readInt()
{
	char c=getchar_unlocked();
	bool neg=false;
	int r=0;
	while (c < '-')	c=getchar_unlocked();
	if (c == '-')	neg=true, c=getchar_unlocked();
	while (c >= '0')
	{
		r = r*10 + c - '0';
		c=getchar_unlocked();
	}
	return neg? -r : r;
}
vector<pair<int, int>>zap[MXN], re[MXN];
vector<int>roz[MXN];
int dl[MXN], ind[2][MXN], x[MXN], y[MXN];
int main()
{
	int n, k, q;
	n=readInt();
	k=readInt();
	q=readInt();
	for (int i=1; i<=n; i++)
	{
		a[i]=readInt();
		s[i]=s[i-1]+a[i];
	}
	for (int i=0; i<q; i++)
	{
		x[i]=readInt();
		y[i]=readInt();
		int l=x[i], r=y[i];
		dl[i]=r-l+1;
		zap[l].push_back(mp(r, i));
		re[r].push_back(mp(l, i));
		roz[dl[i]].push_back(i);
	}
	for (int i=1; i<=n; i++)
	{
		ind[0][i]=zap[i].size()-1;
		ind[1][i]=re[i].size()-1;
		sort(zap[i].begin(), zap[i].end());
		sort(re[i].begin(), re[i].end(), greater<>());
	}
	memset(odp, -1, sizeof(odp));
	for (int i=n; i>=1; i--)
	{
		for (int j=0; j<(int)roz[i].size(); j++)
		{
			int nr=roz[i][j], l=x[nr], r=y[nr];
			if (odp[nr]!=-1)	continue;
			odp[nr]=0;
			while (ind[0][l]>=0 && odp[zap[l][ind[0][l]].s] != -1)	ind[0][l]--;
			while (ind[1][r]>=0 && odp[re[r][ind[1][r]].s] != -1)	ind[1][r]--;
			if (ind[1][r]==-1 || (ind[0][l]!=-1 && dl[zap[l][ind[0][l]].s] > dl[re[r][ind[1][r]].s]))
			{
				int pom=min(k, r-l+2);
				memset(dp+l-1, 0, 8*pom);
				for (int u=l+k-1; u<=r; u+=2)
				{
					int t=u-k;
					dp[u]=max(dp[u-1] , s[u]-s[t]+dp[t]);
					dp[u+1]=max(dp[u] , s[u+1]-s[t+1]+dp[t+1]);
				}
				odp[nr]=dp[r];
				for (; ind[0][l]>=0; ind[0][l]--)	odp[zap[l][ind[0][l]].s]=dp[zap[l][ind[0][l]].f];
			}
			else
			{
				int pom=max(l, r-k+1);
			//	for (int u=l; u<=r+1; u++)	dp[u]=0;
				memset(dp+pom, 0, 8*(r-pom+2));
				for (int u=r-k+1; u>=l; u--)
				{
					int t=u+k;
					dp[u]=max(dp[u+1] , s[t-1]-s[u-1]+dp[t]);					
				}
				odp[nr]=dp[l];
				for (; ind[1][r]>=0; ind[1][r]--)	odp[re[r][ind[1][r]].s]=dp[re[r][ind[1][r]].f];
			}
		}
	}
	for (int i=0; i<q; i++)
	{
		printf("%lld\n", odp[i]);
	}
	return 0;
}
/*
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
*/