#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
using ll=long long;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int Nmax=100005,mod=666013;
ll a[Nmax],sol[Nmax],last[Nmax],aint[4*Nmax];
struct question{
    int l;
    int r;
    int poz;
    bool operator <(question cmp)
    {
        return (r<cmp.r);
    }
};
question q[Nmax];
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        aint[nod]=(aint[nod]+val)%mod;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) update(2*nod,st,mij,poz,val);
    else update(2*nod+1,mij+1,dr,poz,val);
    aint[nod]=(aint[2*nod]+aint[2*nod+1])%mod;
    return;
}
ll query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        return aint[nod]%mod;
    }
    int mij=(st+dr)/2;
    if(b<=mij) return query(2*nod,st,mij,a,b)%mod;
    if(a>mij) return query(2*nod+1,mij+1,dr,a,b)%mod;
    return (query(2*nod,st,mij,a,mij)+query(2*nod+1,mij+1,dr,mij+1,b))%mod;
}
int main()
{
    int n,k,m;
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        fin>>q[i].l;
        fin>>q[i].r;
        q[i].poz=i;
    }
    sort(q+1,q+m+1);
    int j=1;
    for(int i=1;i<=n;i++)
    {
        update(1,1,n,i,a[i]);
        if(last[a[i]]!=0) update(1,1,n,last[a[i]],-a[i]);
        last[a[i]]=i;
        while(q[j].r==i)
        {
            sol[q[j].poz]=query(1,1,n,q[j].l,q[j].r)%mod;
            j++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        fout<<sol[i]<<'\n';
    }
    return 0;
}