#include <bits/stdc++.h>
#define  cin fin
#define cout fout
#define int long long
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int mod=666013;
int aib[100005];
int a[100005];
int ans[100005];
int poz[100005];
vector<int> v[100005];
int n , k , q;
vector<pair<pair<int , int> , int>> intrebari;
bool comparator(pair<pair<int , int> , int> a , pair<pair<int , int> , int> b){
    return a.first.first<b.first.first;
}

void update(int pos , int val){
    for(int i=pos ; i<=n ; i+=(i&(-i))){
        aib[i]+=val;
    }
}
void del (int i){
    int x=a[i];
    if (poz[x]==v[x].size ())return;

    update (v[x][poz[x]],x);
    poz[x]++;
}
int query(int pos){
    int sum=0;
    for(int i=pos ; i>0 ; i-=(i&(-i))){
        sum+=aib[i];
    }
    return sum;
}
int realquery(int l , int r){
    return query(r)-query(l-1);
}
void solvequery (pair<pair<int , int> , int> a){
    ans[a.second]=realquery(a.first.first ,a.first.second);
}
signed main()
{
    cin>>n>>k>>q;
    for(int i=1; i<=n ;i++)
    {
        cin>>a[i];
        v[a[i]].push_back(i);
    }
    for (int i=1;i<=n;++i){
        if (v[i].size ()){
            update (v[i][0],i);
            poz[i]=1;
        }
    }
    for(int i=1 ;i<=q; i++)
    {
        int x , y;cin>>x>>y;
        intrebari.push_back({{x , y} , i});
    }
    sort(intrebari.begin() , intrebari.end(), comparator);
    int j=0;
    for (int i=1;i<=n;++i){
        while (j<=q and intrebari[j].first.first==i){
            solvequery (intrebari[j]);
            j++;
        }
        del (i);
    }

    for (int i=1;i<=q;++i){
        cout <<ans[i]%mod<<'\n';
    }
    return 0;
}