#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);
}

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

    if(sum[nod] != 0)
    {
        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,long long val)
{
    if(lt > y || rt< x) return;
    if(x <= lt && rt <= y)
    {
        sum[nod] += val;
        return;
    }

    int md=(lt+rt)/2;

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

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)
        {
            update(1,1,n,pos[v[st]][lst[v[st]]],pos[v[st]][lst[v[st]]+1]-1,-v[st]); //-v[st]
            lst[v[st]]++;
            ++st;
        }
        while(fn < q[i].y)
        {
            ++fn;
            if(pos[v[fn]][lst[v[fn]]]==fn) update(1,1,n,fn,n,v[fn]);
        }

        s = gett(1,1,n,q[i].y);

        rez[q[i].i]=s%MOD;
        //cout<<"index: "<<i<<endl;
    }
    for(int i=1;i<=m;++i) g<<rez[i]<<'\n';
    return 0;
}