#include <fstream>
#include <algorithm>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int v[100001],aint[400001],fr[100001],sol[100001];
int x,y,n,m,k,s,poz,val;
struct query
{
    int a,b,poz;
}q[100001];
bool cmp(query x,query y)
{
    if(x.b==y.b)
        return x.a<y.a;
    return x.b<y.b;
}
void query(int nod, int st, int dr)
{
    if(x<=st&&dr<=y)
    {
        s=(s+aint[nod])%mod;
        return;
    }
    int mid=(st+dr)/2;
    if(x<=mid)
        query(2*nod,st,mid);
    if(y>mid)
        query(2*nod+1,mid+1,dr);
}
void update(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod]+=val;
        return;
    }
    int mid=(st+dr)/2;
    if(poz<=mid)
        update(2*nod,st,mid);
    else
        update(2*nod+1,mid+1,dr);
    aint[nod]=(aint[2*nod]+aint[2*nod+1])%mod;
}
int main()
{
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int i=1;i<=m;i++)
    {
        fin>>q[i].a>>q[i].b;
        q[i].poz=i;
    }

    sort(q+1,q+m+1,cmp);
    int start=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=start;j<=q[i].b;j++)
        {
            if(fr[v[j]]!=0)
            {
                poz=fr[v[j]],val=-v[j];
                update(1,1,n);
            }
            fr[v[j]]=j;
            val=v[j],poz=j;
            update(1,1,n);
        }
        start=q[i].b+1;
        x=q[i].a,y=q[i].b;
        s=0;
        query(1,1,n);
        sol[q[i].poz]=s;
    }
    for(int i=1;i<=m;i++)
        fout<<sol[i]<<'\n';
    return 0;
}