#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
ifstream fin("distincte.in"); ofstream fout("distincte.out");
#define cin fin
#define cout fout
#define MOD 666013


int t, n, m, k, a[100010];
vector<pair<pii, int> > q;
int fw[100010];
int lt[100010];
bool tr[100010];

void update(int l, int r){
if(l==r){return;}

for(int i=l; i<=r; i++){
    if(i==0){continue;}
    tr[lt[a[i] ] ]=false;
    tr[i]=true;
    for(int j=lt[a[i] ]; j<=n && lt[a[i] ]>0; j+=(j&(-j))){
        fw[j]-=a[i];
    }

    for(int j=i; j<=n; j+=(j&(-j))){
        fw[j]+=a[i];
    }

    lt[a[i] ]=i;
}

return;
}



int query(int l, int r){
int res=0;
for(int j=r; j>=1; j-=(j&(-j))){
    res+=fw[j];
}
for(int j=l-1; j>=1; j-=(j&(-j))){
    res-=fw[j];
}

return res;
}


int rs[100010];




int32_t main(){
INIT
cin>>n>>k>>m;
for(int i=1; i<=n; i++){
    cin>>a[i];
}
for(int g=1; g<=m; g++){
    int i, j;
    cin>>i>>j;
    q.pb(mp(mp(j, i), g) );
}
sort(q.begin(), q.end());



int r=0;
for(int i=0; i<q.size(); i++){
swap(q[i].ft.ft, q[i].ft.sc);
update(r, q[i].ft.sc);
r=q[i].ft.sc;
rs[q[i].sc ]=query(q[i].ft.ft, q[i].ft.sc);
}
for(int i=1; i<=m;i++){
    cout<<rs[i]%MOD<<"\n";
}







return 0;
}