#include <iostream>
using namespace std;
#define MOD 666013
int N, K, M;
int Val, Pos, start, finish;
int elem[100005], lst[100005];
int sum, S[100005], SumArb[20*100005];
struct OffQuery {
    int st;
    int dr;
    int pos;
} off[100005];

int cmp(OffQuery a, OffQuery b) {
    if(a.dr!=b.dr) { return a.dr<b.dr; }
    else if(a.st!=b.st) { return a.st>b.st; }
    return a.pos<b.pos;
}

void Update(int nod, int left, int right) {
    if(left==right) {
         SumArb[nod]=Val;
         return;
    }
    
    int mij=(left+right)/2;
    if(Pos<=mij) { Update(2*nod, left, mij); }
    else { Update(2*nod+1, mij+1, right); }
    
    SumArb[nod]=(SumArb[2*nod]+SumArb[2*nod+1])%MOD;
}

void Query(int nod, int left, int right) {
    if(start<=left && right<=finish) {
         sum+=SumArb[nod]; sum=sum%MOD;
         return;
    }
    
    int mij=(left+right)/2;
    if(start<=mij) { Query(2*nod, left, mij); }
    if(mij<finish) { Query(2*nod+1, mij+1, right); }     
}

int main() {
    FILE *f1=fopen("distincte.in", "r"), *f2=fopen("distincte.out", "w");
    int i, p, nr=1;
    fscanf(f1, "%d%d%d", &N, &K, &M);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d", &elem[i]);
         Val=elem[i]; Pos=i;
         Update(1, 1, N);
    }
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d%d", &off[i].st, &off[i].dr);
         off[i].pos=i;
    }
    off[M+1].st=-1; off[M+1].dr=-1; off[M+1].pos=-1;
    sort(off+1, off+M+1, cmp);
    lst[elem[1]]=1;
    for(i=2; i<=N; i++) {
         if(!lst[elem[i]]) {
              lst[elem[i]]=i;
         }
    }
    for(i=1; i<=N; i++) {
         if(lst[elem[i]]!=i) {
              p=lst[elem[i]]; //elem[p]=0;
              Val=0; Pos=p;
              Update(1, 1, N);
         }
         lst[elem[i]]=i;
         if(i==off[nr].dr) {
              //aflu suma pe intervalul off[nr].st -> off[nr].dr
              sum=0;
              start=off[nr].st; finish=off[nr].dr;
              Query(1, 1, N);
              S[off[nr].pos]=sum;
              nr++; i--;
         }
    }
    for(i=1; i<=M; i++) {
         fprintf(f2, "%d\n", S[i]);
    }
    fclose(f1); fclose(f2);
    return 0;
}