#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 100010
#define MOD 666013

int n, k, m, aib[nmax], s[nmax], t[nmax], p[nmax], v[nmax];

struct nr
{
	int x, y, p, r;
} q[nmax];

int cmp(nr a, nr b)
{
	return a.x<b.x;
}

int cmp2(nr a, nr b)
{
	return a.p<b.p;
}

void update(int poz, int val)
{
	while (poz<=n+1)
	{
		aib[poz]=(aib[poz]+val)%MOD;
		poz += (poz^(poz-1))&poz;
	}
}

int query(int poz)
{
	int s=0;
	while (poz>0)
	{
		s=(s+aib[poz])%MOD;
		poz -= (poz^(poz-1))&poz;
	}
	return s;
}

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	scanf("%d %d %d",&n,&k,&m);
	int i, c;
	for (i=1; i<=n; i++) 
	{
		scanf("%d",&v[i]);
		s[i]=(s[i-1]+v[i])%MOD;
	}
	for (i=1; i<=k; i++) p[i]=n+1;
	for (i=n; i>0; i--) 
	{
		t[i]=p[v[i]];
		p[v[i]]=i;
	}
	for (i=1; i<=n; i++) update(t[i], v[i]);
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d",&q[i].x, &q[i].y);
		q[i].p=i;
	}
	sort(q+1, q+m+1, cmp);
	c=1;
	for (i=1; i<=m; i++)
	{
		for (; c<q[i].x; c++) update(t[c], -v[c]);
		q[i].r=s[q[i].y]-s[q[i].x-1]-query(q[i].y);
		if (q[i].r<0) q[i].r+=MOD;
		if (q[i].r<0) q[i].r+=MOD;
	}
	sort(q+1, q+m+1, cmp2);
	for (i=1; i<=m; i++) printf("%d\n",q[i].r);
}