#include <bits/stdc++.h>
#define nmx 100005
#define mod 666013
using namespace std;
long long n,k,m,v[nmx],arb[4*nmx],prv[nmx],rsp[nmx];
struct edge
{
    int st,dr,i;
};
edge q[nmx];
bool cmp(edge a,edge b)
{
    return a.dr<b.dr;
}
void update(int st,int dr,int index,int pz,long long val)
{
    if (st==dr)
    {
        arb[index]=val;
        return;
    }
    int mid=(st+dr)/2;
    if (pz<=mid)
        update(st,mid,index*2,pz,val);
    else
        update(mid+1,dr,index*2+1,pz,val);
    arb[index]=arb[index*2]+arb[index*2+1];
}
long long query(int st,int dr,int a,int b,int index)
{
    if (a<=st && dr<=b)
        return arb[index];
    if (dr<a || b<st)
        return 0;
    int mid=(st+dr)/2;
    return query(st,mid,a,b,index*2)+query(mid+1,dr,a,b,index*2+1);
}
int main()
{
    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].st>>q[i].dr;
        q[i].i=i;
    }
    sort (q+1,q+m+1,cmp);
    int i=1;
    for (int j=1; j<=m; j++)
    {
        while (i<=q[j].dr)
        {
            if (prv[v[i]])
                update(1,n,1,prv[v[i]],0);
            prv[v[i]]=i;
            update(1,n,1,i,v[i]);
            i++;
        }
        rsp[q[j].i]=query(1,n,q[j].st,q[j].dr,1);
    }
    for (int i=1; i<=m; i++)
        g<<rsp[i]%mod<<'\n';
}