#include<cstdio>
#include<algorithm>
using namespace std;
const int MOD = 666013;
const int NMAX = 100005;
int N,K,M,i,j,A[NMAX],Last[NMAX],AIB[NMAX],Sol[NMAX];
struct Query {int x,y,i;} Q[NMAX];
bool cmp(Query A,Query B) {return A.y<B.y;}
void Update(int poz,int val)
{
    for(int i=poz;i<=N;i+=i&(-i))
        AIB[i]=(AIB[i]+val+MOD)%MOD;
}
int Query(int poz)
{
    int r=0;
    for(int i=poz;i;i-=i&(-i))
        r=(r+AIB[i])%MOD;
    return r;
}
int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	scanf("%d%d%d",&N,&K,&M);
	for(i=1;i<=N;i++) scanf("%d",&A[i]);
	for(i=1;i<=M;i++)
	{
	    scanf("%d%d",&Q[i].x,&Q[i].y);
	    Q[i].i=i;
	}
	sort(Q+1,Q+M+1,cmp);
	for(i=1;i<=M;i++)
	{
	    for(j=Q[i-1].y+1;j<=Q[i].y;j++)
	    {
	        if(Last[A[j]]) Update(Last[A[j]],-A[j]);
	        Update(j,A[j]);
	        Last[A[j]]=j;
	    }
	    Sol[Q[i].i]=(Query(Q[i].y)-Query(Q[i].x-1)+MOD)%MOD;
	}
	for(i=1;i<=M;i++) printf("%d\n",Sol[i]);
	return 0;
}