#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 100000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}
char buf2[BUF_SIZE];
int pos2;
inline void putch(char ch){
    buf2[pos2++]=ch;
    if(pos2==BUF_SIZE) fwrite(buf2, BUF_SIZE, 1, fo), pos2=0;
}

inline void baga(int x){
    char s[10];
    int k=0;
    do{
        s[k++]=x%10+'0';
        x/=10;
    }while(x);
    while(k>0){
        k--;
        putch(s[k]);
    }
}

#define MOD 666013
#define zeros(x) (x&(-x))
int w[MAXN+1], n;
int aib[MAXN+1], last[MAXN+1];
inline void update(int poz, int val){
    for(int i=poz;i<=n;i+=zeros(i)){
        aib[i]=aib[i]+val;
        if(aib[i]>MOD)
            aib[i]-=MOD;
        if(aib[i]<0)
            aib[i]+=MOD;
    }
}
inline int query(int poz){
    int sum=0;
    for(int i=poz;i>0;i-=zeros(i)){
        sum=sum+aib[i];
        if(sum>MOD)
            sum-=MOD;
    }
    return sum;
}

struct Butelie{
    int left, right, pos;
} asparagus[MAXN+1];
int ans[MAXN+1];

bool compare(Butelie x, Butelie y){
    return x.right<y.right;
}

int main(){
    fi=fopen("distincte.in","r");
    fo=fopen("distincte.out","w");
    n=nextnum();
    int k=nextnum(), m=nextnum();
    for(int i=1;i<=n;i++)
        w[i]=nextnum();
    for(int i=1;i<=m;i++){
        asparagus[i].left=nextnum();
        asparagus[i].right=nextnum();
        asparagus[i].pos=i;
    }
    std::sort(asparagus+1, asparagus+1+m, compare);
    int j=1;
    for(int i=1;i<=n;i++){
        update(i, w[i]);
        if(last[w[i]])
            update(last[w[i]], -w[i]);
        last[w[i]]=i;
        while(j<=m && asparagus[j].right==i){
            ans[asparagus[j].pos]=query(asparagus[j].right)-query(asparagus[j].left-1);
            if(ans[asparagus[j].pos]<0)
                ans[asparagus[j].pos]+=MOD;
            j++;
        }
    }
    for(int i=1;i<=m;i++){
        baga(ans[i]);
        putch('\n');
    }
    if(pos2>0) fwrite(buf2, pos2, 1, fo);
    fclose(fi);
    fclose(fo);
    return 0;
}