#include <cstdio>
#include <vector>
#define nmax 100005

using namespace std;

int a[nmax],v[nmax],N,K,Q,AIB[nmax],urm[nmax],sol[nmax];

struct Coord{
 int poz,st;
};
vector<Coord>C[nmax];
vector<Coord>::iterator it;

inline void Update(int x, int poz){
 for(int i = poz; i <= N; i+=(i&-i))
    AIB[i]+=x;
}
inline int Compute(int x){
  int s=0;
 for(int i = x; i; i-=(i&-i))
    s=(s+AIB[i])%666013;
 return s;
}
int main(){
    int i,l,r;
    Coord w;
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    scanf("%d%d%d\n",&N,&K,&Q);
    for(i = 1; i <= N; ++i)
        scanf("%d\n",&a[i]);

    for(i = N; i; --i)
        if(!v[a[i]]) v[a[i]] = i,urm[i] = N+1;
        else urm[i] = v[a[i]],v[a[i]] = i;
    for(i = 1; i <= Q; ++i){
        scanf("%d%d\n",&l,&r);
        w.poz = i,w.st = l;
        C[r].push_back(w);
    }
    for(i = 1; i <= N; ++i){
        Update(a[i],i);
        Update(-a[i],urm[i]);

      for(it = C[i].begin();it!=C[i].end();++it)
        sol[it->poz] = Compute(i);
    }
     for(i=1;i<=Q;++i)
        printf("%d\n", sol[i]);
    return 0;
}