#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)
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];

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

    int x, y;
    for(int i=1; i<=m; ++i){
        f >> x >> 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 debug(){
    for(int i=1; i<=n; ++i) cout << urm[ poz[i] ] << " ";
    cout << "\n";
    for(int i=1; i<=n; ++i) cout << poz[i] << " ";
    cout << "\n";

    for(int i=1; i<=m+n; ++i){
        if (Q[i].second.first != inf){
            cout << vec[i] << "\n";
        }
    }
}
/*
void update(int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }else{
        int mij = (st + dr) / 2;
        if (poz <= mij) update(nod*2, st, mij, poz, val);
                   else update(nod*2+1, mij+1, dr, poz, val);

        aint[nod] = aint[nod*2] + aint[nod*2+1];
    }
}

void query(int nod, int st, int dr, int a, int b, int &sum){
    if (a <= st && dr <= b){
        sum += aint[nod];
        return;
    }else {
        int mij = (st + dr) / 2;
        if (a <= mij) query(nod*2, st, mij, a, b, sum);
        if (b > mij) query(nod*2+1, mij+1, dr, a, b, sum);
    }
}
*/

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

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

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);
    //debug();

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

    for(int i=1; i<=n+m; ++i){
        //cout << i << " " << Q[i].second.first << "\n";
        if (Q[i].first.second == 0){//e din a[]
            //cout << Q[i].first.first << "\n";
            //update(1, 1, n, pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
            update(pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
        }else{//e query
            int sum = 0;
            int Poz = 1;
            //int Poz = cb(0, n+1, Q[i].second.first+1);// ma intereseaza unde s-ar afla y-ul din query in vectorul urm[]
            //query(1, 1, n, Poz, n, sum);
            //cout << Q[i].first.first << " " << Q[i].second.first << " " << sum << "\n";
            //vec[ i ] = sum;// pe asta o sa o scad;
            Q[i].second.second = ( query(n) - query(Poz-1) );
            //cout <<( query(n) - query(Poz-1) )<< "\n";
        }
    }
}

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
            //cout << Q[i].second.second << "\n";
            //update(1, 1, n, pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
            update(pozS[ Q[i].second.second ], a[ Q[i].second.second ]);
        }else {
            int sum = 0; int Poz = cb(0, n+1, Q[i].second.first+1);
            //query(1, 1, n, Poz, n, sum);
            //cout << Q[i].first.first << " " << Q[i].second.first << " " << Poz << "\n";
            rez[ Q[i].first.second ] = ( query(n) - query(Poz-1) ) - Q[i].second.second;
            //rez[ Q[i].first.second ] = Q[i].second.second;
        }
    }

    for(int i=1; i<=m; ++i)
        g << rez[i] % MOD << "\n";
    //debug();
}

int main(){
    citeste();
    rezolva();

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

    return 0;
}