#include <cstdio>
#include <algorithm>
#define NMAX 100005
#define LSB(x) ((-x)&x)
#define MOD 666013

using namespace std;

int n,m,k,i,a,b,ind,j;
int v[NMAX],viz[NMAX],ant[NMAX];
int AIB[NMAX];

struct punct
{
    int a,b,sol,p;
}q[NMAX];

bool cmp(punct r,punct p)
{
    return(r.b<p.b);
}
bool cmp2(punct r,punct p)
{
    return (r.p<p.p);
}

int sum(int x)
{
    int S=0;
    for(int i=x; i>0; i-=LSB(i))
        S += AIB[i];
    return S;
}

void update(int poz,int x)
{
    for(int i=poz; i<=n; i+=LSB(i))
        AIB[i]+=x;
}

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);

    for(i=1;i<=n;++i)
        {
            scanf("%d",&v[i]);
            ant[i]=n+1;
        }

    for(i=1;i<=m;++i)
        {
            scanf("%d%d",&q[i].a,&q[i].b);
            q[i].p=i;
        }
    sort(q+1,q+m+1,cmp);

    ind=1;
    for(i=1; i<=m; ++i)
    {
        while(ind <= q[i].b)
        {
            //adaugam la AIB
            update(ant[v[ind]],-v[ind]);
            update(ind,v[ind]);
            ant[v[ind]]=ind;
            ++ind;
        }
        q[i].sol=(sum(q[i].b)-sum(q[i].a))%MOD;
    }

    sort(q+1,q+m+1,cmp2);
    for(i=1;i<=m;++i)
        printf("%d\n",q[i].sol);
    return 0;
}