#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>


#define DN 100005
#define MOD 666013
#define f first
#define s second
using namespace std;

struct st{
    pair<int,int> val;
    int indice;
};

int v[DN],aib[DN],poz[DN],n,m,k;
vector< pair<int,int> >rez;
st q[DN];



inline int lsb(int x)
{
    return (x&(x-1))^x;
}
bool cmp(st a,st b)
{
    if(a.val.s==b.val.s)
        return a.val.f<b.val.f;
    return a.val.s<b.val.s;
}

void update(int poz,int val)
{
    for(;poz<=n;poz+=lsb(poz))
        aib[poz]=(aib[poz] + MOD + val )%MOD;
}

int query(int poz)
{
    int rez=0;
    for(;poz>=1;poz-=lsb(poz))
        rez=(rez + aib[poz])%MOD;
    return rez;
}


int main()
{
    int ind=1;
    ifstream f("distincte.in");
    ofstream g("distincte.out");
    f>>n>>k>>m;
    for(int i=1;i<=n;++i)
        f>>v[i];

    for(int i=1;i<=m;++i)
    {
        f>>q[i].val.f>>q[i].val.s;
        q[i].indice=i;
    }

    sort(q+1,q+m+1,cmp);

    for(int i=1;i<=m;++i)
    {
        for(;ind<=q[i].val.s;++ind)
        {
            int x = v[ind];
            if(poz[x])
                update( poz[x], -x);
            poz[x]=ind;
            update( poz[x], x );
        }
        rez.push_back( make_pair ( q[i].indice, (query(q[i].val.s) + MOD -query(q[i].val.f-1) )%MOD ));

       /* for(int j=1;j<=n;++j)*
            cout<<j<<" "<<aib[j]<<endl;*/
    }
    sort(rez.begin(),rez.end());
    for(int i=0;i<rez.size();++i)
        g<<rez[i].s<<"\n";
    return 0;
}