#include <fstream.h>
int main()
{
ifstream f("distincte.in");
ofstream g("distincte.out");
int i,*v,*luat,u1,u2,n,s,k,j,m;
f>>n>>k>>m;
v=new int[n+1];
luat=new int[k];
for (i=1;i<=n;i++)
	f>>v[i];
for (i=1;i<=m;i++)
	{
	s=0;
	f>>u1>>u2;
	for (j=1;j<=k;j++)
		luat[j]=0;
	for (j=u1;j<=u2;j++)
		if (!luat[v[j]])
			{
			luat[v[j]]=1;
			s+=v[j];
			}
	g<<s%666013<<"\n";
	}
f.close();
g.close();
return 0;
}