#include<stdio.h>
#include<string.h>
int N,K,M;
int A[100001],v[100001];
int main()
{
    int i,x,y,j,S;
    freopen("distincte.in","r",stdin);
    scanf("%d%d%d",&N,&K,&M);
    for(i=1;i<=N;i++)
        scanf("%d",&A[i]);
    freopen("distincte.out","w",stdout);
    for(i=1;i<=M;i++)
    {
        memset(v,0,sizeof(v));
        scanf("%d%d",&x,&y);
        S=0;
        for(j=x;j<=y;j++)
            if(v[A[j]]==0)
            {
                S=(S+A[j])%666013;
                v[A[j]]=1;
            }
        printf("%d\n",S);
    }
    fclose(stdout);
    return 0;
    
}