#include <bits/stdc++.h>
#define ll long long
#define DIM 100005
#define MOD 666013
using namespace std;
int v[DIM],tree[DIM*4],last[DIM],p[DIM];
struct question{
   int le,ri,pos,sol;
};
question q[DIM];
bool cmp1(question a,question b) {
   return a.ri<b.ri;
}
bool cmp2(question a,question b) {
  return a.pos<b.pos;
}

int a,b,pos,val,ans;
void update(int node,int l,int r) {
    if (l==r) tree[node]=val;
    else {
        int mid=(l+r)/2;
        if (pos<=mid) update(2*node,l,mid);
        else update(2*node+1,mid+1,r);
        tree[node]=(tree[2*node]+tree[2*node+1])%MOD;
    }
}
void query(int node,int l,int r) {
    if (a<=l && r<=b) ans=(ans+tree[node])%MOD;
    else {
         int mid=(l+r)/2;
         if (a<=mid) query(2*node,l,mid);
         if (mid<b) query(2*node+1,mid+1,r);
    }
}
int main()
{   int n,m,k,i,j;
    ifstream f("distincte.in");
    ofstream g("distincte.out");
    f>>n>>k>>m;
    for (i=1;i<=n;++i) {
        f>>v[i],val=v[i],pos=i,update(1,1,n);
        last[i]=p[v[i]];
        p[v[i]]=i;
    }

    for (i=1;i<=m;++i)
        f>>q[i].le>>q[i].ri,q[i].pos=i;
    sort(q+1,q+m+1,cmp1);

    j=1;
    for (i=1;i<=n;++i) {
       if (last[i]) pos=last[i],val=0,update(1,1,n);
        while (q[j].ri==i) {
            a=q[j].le,b=q[j].ri,ans=0;
            query(1,1,n);
            q[j].sol=ans;
            ++j;
        }
    }

    sort(q+1,q+m+1,cmp2);
    for (i=1;i<=m;++i)
        g<<q[i].sol<<'\n';

    return 0;
}