#include <bits/stdc++.h>
#define MOD 666013
#define maxN 100005
#define UB(x) ((x)&(-x))
using namespace std;
int n,m,j,k,i;
int poz[maxN];
int aib[maxN];
int sol[maxN];
struct quer
{
    int st,dr,ind;
}q[maxN];
int v[maxN];
bool cmp(quer a,quer b)
{
    return a.dr<b.dr;
}
void update(int pos,int val)
{
    int x;
    for(x=pos;x<=n;x+=UB(x))
        aib[x]=(aib[x]+val)%MOD;
}
int query(int pos)
{
    int s=0,x;
    for(x=pos;x>0;x-=UB(x))
        s=(s+aib[x])%MOD;
    return s;
}
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d %d %d\n",&n,&k,&m);
    for(i=1;i<=n;i++)
        scanf("%d\n",&v[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d\n",&q[i].st,&q[i].dr);
        q[i].ind=i;
    }
    j=1;
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=q[m].dr;i++)
    {
        if(poz[v[i]])
            update(poz[v[i]],-v[i]);
        update(i,v[i]);
        poz[v[i]]=i;
        while(i==q[j].dr)
        {
            sol[q[j].ind]=(query(q[j].dr)-query(q[j].st-1))%MOD;
            while(sol[q[j].ind]<0)
                sol[q[j].ind]+=MOD;
            j++;
        }
    }
    for(i=1;i<=m;i++)
        printf("%d\n",sol[i]);
    return 0;
}