#include <bits/stdc++.h>

using namespace std;

const long long N=100005;
const int MOD=666013;

ifstream f("distincte.in");
ofstream g("distincte.out");

vector<long long> pos[N];
long long lst[N],sum[4*N],v[N];
long long n,k,m,x,y;
long long st,fn;
long long rez[N];
long long s;

struct Query{
    long long x,y,i;
}q[N];

bool comp(Query A,Query B)
{
    if(A.x == B.x) return (A.y < B.y);
    return (A.x < B.x);
}

void sett(int nod,int lt,int rt,int pos)
{
    if(lt == rt)
    {
        sum[nod] = s;
        return;
    }

    int md = (lt+rt)/2;

    if(pos<=md) sett(nod*2,lt,md,pos);
    else sett(nod*2+1,md+1,rt,pos);
}

long long gett(int nod,int lt,int rt,int pos)
{
    if(lt == rt) return sum[nod];

    if(sum[nod])
    {
        sum[nod*2] += sum[nod];
        sum[nod*2+1] += sum[nod];
        sum[nod] = 0;
    }

    int md = (lt+rt)/2;

    if(pos<=md) return gett(nod*2,lt,md,pos);
    else return gett(nod*2+1,md+1,rt,pos);
}

void update(int nod,int lt,int rt,int x,int y)
{
    if(lt > y || rt< x) return;
    if(x <= lt && rt <= y)
    {
        sum[nod] -= v[st];
        return;
    }

    int md=(lt+rt)/2;

    if(md >= x) update(nod*2,lt,md,x,y);
    if(md < y) update(nod*2+1,md+1,rt,x,y);
}

int main()
{
    f>>n>>k>>m;
    for(long long i=1;i<=n;++i)
    {
        f>>x;
        pos[x].push_back(i);
        v[i]=x;
    }
    for(int i=1;i<=k;++i)
    {
        pos[i].push_back(n+1);
        lst[i] = 0;
    }
    for(long long i=1;i<=m;++i)
    {
        f>>q[i].x>>q[i].y;
        q[i].i=i;
    }
    sort(q+1,q+m+1,comp);
    st=q[1].x;
    for(long long i=1;i<=m;++i)
    {
        while(st < q[i].x)
        {
            //cout<<"upd: "<<pos[v[st]][lst[v[st]]]<<' '<<min(fn,pos[v[st]][lst[v[st]]+1]-1)<<endl;
            update(1,1,n,pos[v[st]][lst[v[st]]],min(fn,pos[v[st]][lst[v[st]]+1]-1)); //v[st]
            lst[v[st]]++;
            ++st;
        }
        if(fn != 0) s = gett(1,1,n,min(fn,q[i].y));
        while(fn < q[i].y)
        {
            ++fn;
            if(pos[v[fn]][lst[v[fn]]]==fn) s+=v[fn];
            //cout<<"sett: "<<fn<<"sum: "<<s<<endl;
            sett(1,1,n,fn);
        }
        rez[q[i].i]=s%MOD;
        //cout<<"index: "<<i<<endl;
    }
    for(int i=1;i<=m;++i) g<<rez[i]<<'\n';
    return 0;
}