#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int nmax=100000,MD=666013;
long long ai[nmax+5];
int lsb[nmax+5];
struct sp
{
    int st,dr,po;
} inter[nmax+5];
long long ans[nmax+5];
int in[nmax+5],lv[nmax+5],last[nmax+5];
void update(int val,int p)
{
   for(int i=p;i>0;i=i-lsb[i])
    ai[i]+=val;
}
bool cmp(sp a1,sp a2)
{
    if(a1.dr==a2.dr)
        return a1.st<a2.st;
    return a1.dr<a2.dr;
}
long long query(int st,int dr)
{
   long long ans=0;
   int i;
   for(i=st;i<=nmax;i=i+lsb[i])
    ans+=ai[i];
   for(i=dr+1;i<=nmax;i=i+lsb[i])
    ans-=ai[i];
   return ans;
}
bool ini(sp a1,sp a2)
{
    return a1.po<a2.po;
}
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int n,m,k,i,j;
    scanf("%d%d%d",&n,&k,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&in[i]);
        last[i]=lv[in[i]];
        lv[in[i]]=i;
    }
    for(i=1;i<=nmax;i++)
        lsb[i]= ( i & (-i));
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&inter[i].st,&inter[i].dr);
        inter[i].po=i;
    }
    sort(inter+1,inter+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        for(j=inter[i-1].dr+1;j<=inter[i].dr;j++)
        {
            update(in[j],j);
            if(last[j]!=0)
            update(-in[j],last[j]);
        }
        ans[inter[i].po]=query(inter[i].st,inter[i].dr);

    }
    for(i=1;i<=m;i++)
        {
            if(ans[i]>=MD)
                ans[i]%=MD;
            cout<<ans[i]<<"\n";
        }
    return 0;
}