//#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
bool ms(pair<long long,pair<long long,long long> > a,pair<long long,pair<long long,long long> > b){
    return a.second.first<b.second.first;
}
pair<long long,pair<long long,long long> > query[100005];
long long v[100005];
long long f[100005];
long long aib[100005],n,k,m,ans[100005];
void upd(long long a,long long val){
    for(;a<=n;a+=(a&(-a))){
        aib[a]+=val;
    }
}
long long que(long long a){
    long long sol=0;
    for(;a>=1;a-=(a&-a)){
        sol+=aib[a];
    }
    return sol;
}
int main()
{
    cin>>n>>k>>m;
    for(long long i=1;i<=n;i++){
        cin>>v[i];
    }
    for(long long i=1;i<=m;i++){
        cin>>query[i].first>>query[i].second.first;
        query[i].second.second=i;
    }
    sort(query+1,query+m+1,ms);
    long long cnt=1;
    for(long long i=1;i<=n;i++){
        if(f[v[i]]==0){
            f[v[i]]=i;
            upd(i,v[i]);
        }
        else{
            upd(f[v[i]],-v[i]);
            f[v[i]]=i;
            upd(i,v[i]);
        }
        while(query[cnt].second.first==i and cnt<=m){
            ans[query[cnt].second.second]=que(query[cnt].second.first)-que(query[cnt].first-1);
            cnt++;
        }
    }
    for(long long i=1;i<=m;i++){
        cout<<ans[i]%666013<<"\n";
    }
    return 0;
}