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
113
114
115
116
117
118
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

long long oddz[300009], tab[300009], dp[300009], opt[300009], in_opt[300009];
long long n, k, q;
vector<vector<long long> > ans;

void cnt_opt()
{
	for(int i=1; i<=n; i++)
	{
		if(i >= k) opt[i] = max(opt[i-1], opt[i-k] + oddz[i-k+1]);
		else dp[i] = opt[i-1];
	}
	int a = n, b = opt[n], c = n;
	while(a >= 1)
	{
		if(opt[a] == opt[a-1]) a--;
		else
		{
			c = a - k + 1;
			in_opt[c] = 2;
			in_opt[a] = 3;
			b = opt[c-1];
			opt[c] = b;
			c++;
			while(c < a)
			{
				opt[c] = b;
				in_opt[c] = 1;
				c++;
			}
			a = a - k;
		}
	}
	return;
}

void count_queries()
{
	long long a = 0, b;
	for(int i=1; i<=n; i++)
	{
		cin>>b;
		tab[i] = b;
		a += b;
		if(i >= k)
		{
			oddz[i - k + 1] = a;
			a -= tab[i - k + 1];
		}
	}
	cnt_opt();
	for(int i=1; i<=q; i++)
	{
		cin>>a>>b;
        if(b - a + 1 < k)
        {
            cout<<0<<"\n";
            continue;
        }
        if((in_opt[a] == 0 || in_opt[a] == 2) && (in_opt[b] == 0 || in_opt[b] == 3))
        {
        	cout<<opt[b] - opt[a-1]<<"\n";
        	continue;
        }
		dp[a-1] = 0;
		for(int j=a; j<=b; j++)
		{
			if(j >= a + k - 1) dp[j] = max(dp[j-1], dp[j-k] + oddz[j-k+1]);
			else dp[j] = dp[j-1];
		}
		cout<<dp[b]<<"\n";
	}
	return;
}

void square()
{
	long long a, b;
	ans.resize(n+3);
	for(int i=0; i<=n; i++) ans[i].resize(n+3, 0);
	for(int i=1; i<=n; i++) cin>>tab[i];
	for(int i=1; i<=n; i++)
	{
		a = 0;
		for(int j=i; j<=n; j++)
		{
			a += tab[j];
			if(j >= i + k - 1)
			{
				ans[i][j] = max(ans[i][j-1], ans[i][j-k] + a);
				a -= tab[j - k + 1];
			}
			else ans[i][j] = ans[i][j-1];
		}
	}
	for(int i=1; i<=q; i++)
	{
		cin>>a>>b;
		cout<<ans[a][b]<<"\n";
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>k>>q;
	if(q < n || n > 5000) count_queries();
	else square();
	return 0;
}