#include<fstream>
#include<algorithm>
using namespace std;

struct st
{
	int x,y,z;
};

const int mo=666013;

st a[100001];
int v[100001],b[100001],aib[100001],i,n,m,k,nr,x;

bool cmp(st a,st b)
{
	return a.y<b.y;
}

bool cmp2(st a,st b)
{
	return a.z<b.z;
}

void update(int p,int val)
{
	int i;
	for (i=p;i<=n;i=(i | (i-1))+1)
		aib[i]+=val;
}

int query(int p)
{
	int i,s=0;
	for (i=p;i>=1;i=i & (i-1))
		s=(s+aib[i])%mo;
	return s;
}

int main()
{
	ifstream f("distincte.in");
	ofstream g("distincte.out");
	f >> n >> k >> m;
	for (i=1;i<=n;i++)
		f >> v[i];
	for (i=1;i<=m;i++)
	{
		f >> a[i].x >> a[i].y;
		a[i].z=i;
	}
	sort(a+1,a+m+1,cmp);
	x=1;
	for (i=1;i<=n;i++)
	{
		if (b[v[i]]!=0)
			update(b[v[i]],-v[i]);
		else nr=(nr+v[i])%mo;
		b[v[i]]=i;
		update(i,v[i]);
		while ((x<=m) && (a[x].y==i))
		{
			a[x].x=nr-query(a[x].x-1);
			while (a[x].x<0)
				a[x].x+=mo;
			x++;
		}
	}
	sort(a+1,a+m+1,cmp2);
	for (i=1;i<=m;i++)
		g << a[i].x << "\n";
	return 0;
}