using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 100001
#define Mod 666013
int V[Nm],X[Nm],Y[Nm],Poz[Nm],A[Nm],Ans[Nm],n,k,m;

void read()
{
    int i;

    freopen("distincte.in","r",stdin);
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;++i)
        scanf("%d",V+i);
    for(i=0;i<m;++i)
        scanf("%d%d",X+i,Y+i);
}

bool cmp(int a, int b)
{
    return Y[a]<Y[b];
}

void update(int i, int v)
{
    for(;i<=n;i+=i&(i-1)^i)
    {
        A[i]+=v;
        if(A[i]>=Mod)
            A[i]-=Mod;
        if(A[i]<0)
            A[i]+=Mod;
    }
}

int query(int i)
{
    int ans=0;

    for(;i;i-=i&(i-1)^i)
    {
        ans+=A[i];
        if(ans>=Mod)
            ans-=Mod;
    }
    return ans;
}

void solve()
{
    int I[Nm],i,j;

    for(i=0;i<m;++i)
        I[i]=i;
    sort(I,I+m,cmp);

    j=1;
    for(i=0;i<m;++i)
    {
        while(j<=Y[I[i]])
        {
            update(j,V[j]);
            if(Poz[V[j]])
                update(Poz[V[j]],-V[j]);
            Poz[V[j]]=j++;
        }
        Ans[I[i]]=query(Y[I[i]])-query(X[I[i]]-1);
        if(Ans[I[i]]<0)
            Ans[I[i]]+=Mod;
    }
}

void write()
{
    int i;

    freopen("distincte.out","w",stdout);
    for(i=0;i<m;++i)
        printf("%d\n",Ans[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}