#include <fstream>
#include <algorithm>

using namespace std;

int aib[100005],n,frec[100005],ante[100005],v[100005],real[100005],fin[100005];
#define lsb(x) (x&(-x))
#define mod 666013

void update(int x,int val)
{
    if(x==0)
        return;
    val%=mod;
    real[x]=val;
    for(;x<=n;x+=lsb(x))
        aib[x]=(aib[x]+val)%mod;
}

int query(int x)
{
    int sum=0;
    for(;x>=1;x-=lsb(x))
        sum=(sum+aib[x])%mod;
    return sum;
}

struct segm
{
    int st,dr;
    int init;
}intreb[100005];

bool operator<(const segm &a,const segm &b)
{
    if(a.dr<b.dr)
        return 1;
    else if(a.dr==b.dr)
        if(a.st<b.st)
            return 1;
    return 0;
}

int main()
{
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");

    int m=0,k,i,poz=0;
    cin>>n>>k>>m;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        ante[i]=frec[v[i]];
        //cout<<ante[i]<<' ';
        frec[v[i]]=i;
    }

    for(i=0;i<m;i++)
    {
        cin>>intreb[i].st>>intreb[i].dr;
        intreb[i].init=i;
    }
    sort(intreb,intreb+m);
    for(i=1;i<=n;i++)
    {
        update(ante[i],-real[ante[i]]);
        update(i,v[i]);
        while(intreb[poz].dr==i)
        {
            fin[intreb[poz].init]=(query(intreb[poz].dr)-query(intreb[poz].st-1))%mod;
            poz++;
        }
    }
    for(i=0;i<m;i++)
        cout<<fin[i]<<'\n';
    cin.close();
    cout.close();
    return 0;
}