#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

//ifstream f("distincte.in");
ofstream g("distincte.out");

#define nmax 100005
#define inf (1<<29)
#define ll long long
#define MOD 666013
#define bit(x) (x & -x)
#define Cifmax (1<<14)

int n, K, m, viz[nmax], urm[nmax], vec[nmax*2], poz[nmax], pozS[nmax], a[nmax];
pair< pair<int, int> , pair<int,int> > Q[nmax*2];
int aib[nmax];
int rez[nmax];
int ceva[nmax];
char S[Cifmax];
int pz = 0;

void buf(int &nr){
    nr = 0;
    while( S[pz]<'0' || S[pz]>'9' ){
        ++pz;
        if (pz == Cifmax){
            fread(S, 1, Cifmax, stdin);
            pz = 0;
        }
    }

    while(S[pz]>='0' && S[pz]<='9'){
        nr = nr * 10 + (S[pz] - '0');
        ++pz;
        if (pz == Cifmax){
            fread(S, 1, Cifmax, stdin);
            pz = 0;
        }
    }
}

void citeste(){
    buf(n); buf(K); buf(m);
    for(int i=1; i<=n; ++i) buf(a[i]), Q[i] = make_pair( make_pair(i, 0), make_pair(i, i) );

    int x, y;
    for(int i=1; i<=m; ++i){
        buf(x); buf(y); Q[n+i] = make_pair( make_pair(x, i) , make_pair(y, 0) );
    }
}

void fa_urm(){
    //fac vectorul cu urm
    for(int i=0; i<=K; ++i) viz[i] = n+1;
    for(int i=n; i>=1; --i){
        urm[ i ] = viz[ a[i] ]; viz[ a[i] ] = i;
    }
}

inline bool cmpQuery(pair< pair<int, int >, pair<int,int> > A, pair< pair<int,int>, pair<int,int> > B){
    if (A.first.first == B.first.first){//daca au acelasi x;
        return A.first.second > B.first.second;
    }
    return A.first.first < B.first.first;
}

inline bool cmpPoz(int A, int B){
    return urm[A] < urm[B];
}

int cb(int st, int dr, int val){
    while(dr-st>1){
        int mij = (st + dr) / 2;
        if ( urm[ poz[mij] ] >= val){
            dr = mij;
        }else st = mij;
    }
    return dr;
}

void update(int poz, int val){
    for(; poz<=n; poz+=bit(poz)){
        aib[poz] += val;
        if (aib[poz] >=MOD) aib[poz] -= MOD;
    }
}

int query(int poz){
    int s =0;
    for(; poz>0; poz-=bit(poz)){
        s += aib[poz];
        if (s >= MOD) s-=MOD;
    }
    return s;
}

void fa_cb(){
    for(int i=1; i<=n; ++i){
        ceva[i+1] = cb(0, n+1, i+1);// ma intereseaza unde s-ar afla y-ul din query in vectorul urm[]
    }
}

void baga(){
    sort( Q+1, Q+n+m+1, cmpQuery);//sortez dupa capatul drept;
    // o sa mai am nevoie ca pentru fiecare element din urm[] sa ii stiu ordinea in vectorul sortat crescator;
    for(int i=1; i<=n; ++i) poz[i] = i;
    sort(poz+1, poz+n+1, cmpPoz);
    fa_cb();// preprocesez capatul din dreapta ca sa mai scap de timp;
    //debug();

    for(int i=1; i<=n; ++i) pozS[ poz[i] ] = i;

    for(int i=1; i<=n+m; ++i){
        if (Q[i].first.second == 0){//e din a[]
            update(pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
        }else{//e query
            int Poz = ceva[ Q[i].second.first+1 ];
            Q[i].second.second = ( query(n) - query(Poz-1) + MOD );
            if (Q[i].second.second >= MOD) Q[i].second.second -= MOD;
        }
    }
}

inline bool cmpQ2(pair< pair<int, int >, pair<int,int> > A, pair< pair<int,int>, pair<int,int> > B){// le sortez dupa capatul drept
    //acum un elem apare inainte de query
    if (A.second.first == B.second.first){
        return A.first.second < B.first.second;
    }
    return A.second.first < B.second.first;
}

void rezolva(){
    // tin la fel pentru fiecare i urm[i]; pot face si altfel mai exact;
    // sortez dupa capatul drept query-urile si incep de la 1 si ma tot duc la un query raspunsul va fi suma pe intervalul dr+1,n+1;
    // adica acele distinctere care apar intre 1 si dr dar urmatoare aparitie e in afara intervalului doar ca s-ar putea ca intre dr+1,n+1 sa mai fie
    // ceva numere care nu intra in [st,dr]( apartin intervalului [1,st) ) ; => deci la fiecare query am nevoie de suma numerelor care apar
    // intre dr+1,n+ceva dar nu sunt in [st,dr]
    // asa ca inainte sortez query-urile dupa capatul stang si tin minte pentru fiecare query suma acelor numere;
    // adica pentru un query st,dr eu sunt la pasul st(pe elementul st nu l-am bagat) ma intereseaza suma numerelor de pe intervalul [dr+1,n+1];
    fa_urm();
    baga();

    for(int i=1; i<=n; ++i) aib[i] = 0;

    sort(Q+1, Q+m+n+1, cmpQ2);
    for(int i=1; i<=m+n; ++i){
        if (Q[i].first.second == 0){// e element
            update(pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
        }else {
            int Poz = ceva[ Q[i].second.first+1 ];
            rez[ Q[i].first.second ] = ( query(n) - query(Poz-1) + MOD );
            if ( rez[ Q[i].first.second ] >= MOD ) rez[ Q[i].first.second ] -= MOD;
            rez[ Q[i].first.second ] = rez[ Q[i].first.second ] - Q[i].second.second + MOD;
            if ( rez[ Q[i].first.second ] >= MOD ) rez[ Q[i].first.second ] -= MOD;
        }
    }

    for(int i=1; i<=m; ++i)
        g << rez[i] << "\n";

}

int main(){
    freopen("distincte.in", "r" , stdin);
    citeste();
    rezolva();

    //f.close();
    g.close();

    return 0;
}