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

ifstream in("distincte.in");
ofstream out("distincte.out");

const int N=100005, M=666013;

struct query
{
	int st,dr,ind;
};

bool cmp(query a, query b)
{
	return (a.st<b.st || (a.st==b.st && a.dr<b.dr));
}

query q[N];
int n,m,k;
int use[N],urm[N],poz[N],v[N];
long long aib[N],rez[N];

int step(int x)
{
	return x & (-x);
}

void update(int x,int val)
{
	for(;x<=n;x+=step(x))
		aib[x]+=val;
}

long long query(int x)
{
	long long sum=0;
	
	for(;x;x-=step(x))
		sum+=aib[x];
	
	return sum;
}

int main()
{
	int i,j;
	
	in>>n>>k>>m;
	
	for(i=1;i<=n;i++)
		in>>v[i];
	
	for(i=1;i<=m;i++)
	{
		in>>q[i].st>>q[i].dr;
		q[i].ind=i;
	}
	
	sort(&q[1],&q[m+1],cmp);
	
	for(i=n;i>=1;i--)
	{
		urm[i]=poz[v[i]];
		poz[v[i]]=i;
	}
	
	for(i=1;i<=k;i++)
		if(poz[i])
		{
			update(poz[i],i);
			use[poz[i]]=1;
		}
		
	for(i=1;i<=m;i++)
	{
		for(j=q[i-1].st;j<=q[i].st-1;j++)
		{
			if(use[j])
			{
				use[j]=0;
				update(j,-v[j]);
				
				if(urm[j])
				{
					use[urm[j]]=1;
					update(urm[j],v[j]);
				}
			}
		}
		
		rez[q[i].ind]=query(q[i].dr);
	}
	
	for(i=1;i<=m;i++)
		out<<rez[i]%M<<"\n";
	
	return 0;
}