#include <bits/stdc++.h>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int MAXN=100005;
const int MOD=666013;

int n,k,m;
int a[MAXN],bit[MAXN],last[MAXN];
int l[MAXN],r[MAXN],ans[MAXN];
int head[MAXN],nxt[MAXN];

void update(int p,int x){
    while(p<=n){
        bit[p]=(bit[p]+x)%MOD;
        p+=p&-p;
    }
}

int sum(int p){
    int s=0;
    while(p){
        s=(s+bit[p])%MOD;
        p-=p&-p;
    }
    return s;
}

int main(){
    
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int i=1;i<=m;i++){
        fin>>l[i]>>r[i];
        nxt[i]=head[r[i]];
        head[r[i]]=i;
    }
    for(int i=1;i<=n;i++){
        int x=a[i];
        if(last[x])
            update(last[x],-x);
        update(i,x);
        last[x]=i;
        for(int j=head[i];j;j=nxt[j]){
            ans[j]=sum(r[j])-sum(l[j]-1);
            ans[j]%=MOD;
            if(ans[j]<0)
                ans[j]+=MOD;
        }
    }
    for(int i=1;i<=m;i++)
        fout<<ans[i]<<'\n';
    return 0;
}