#include <fstream>
#include <algorithm>
#define MOD 666013
#define DIM 100005
#define bit(x) ((x&(x-1))^x)
using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

int N,K,M,V[DIM],aib[DIM],poz[DIM],answer[DIM];
struct query{
    int x,y,ord;
};
query C[DIM];
void add(int x,int val){
    for(int i=x;i<=N;i+=bit(i))
        aib[i]=(aib[i]+val+MOD)%MOD;
}
int suma(int x){
    int sum=0;
    for(int i=x;i>0;i-=bit(i))
        sum=(sum+aib[i])%MOD;
    return sum;
}
int cmp(query a,query b){
    return a.y<b.y;
}
int main(){
    fin>>N>>K>>M;

    for(int i=1;i<=N;i++)
        fin>>V[i];

    for(int i=1;i<=M;i++){
        fin>>C[i].x>>C[i].y;
        C[i].ord=i;
    }
    sort(C+1,C+M+1,cmp);

    for(int i=1;i<=M;i++){

        for(int j=C[i-1].y+1;j<=C[i].y;j++){
            if(poz[V[j]])
                add(poz[V[j]],-V[j]);
            add(j,V[j]);
            poz[V[j]]=j;
        }
        answer[C[i].ord]=(suma(C[i].y)-suma(C[i].x-1)+MOD)%MOD;
    }
    for(int i=1;i<=M;i++)
        fout<<answer[i]<<"\n";
    fin.close();fout.close();
    return 0;
}