#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 MOD 666013
#define bit(x) (x & (-x))
#define ll long long

typedef struct camp{
    int x, y, cod;
};
camp q[nmax+nmax];
int n, K, m, a[nmax], rez[nmax], urm[nmax], aib[nmax], viz[nmax];;

void citeste(){
    f >> n >> K >> m;
    for(int i=1; i<=n; ++i){
        f >> a[i];
        q[i].x = i; q[i].y = 0; q[i].cod = 0;
    }

    int x,y;
    for(int i=1; i<=m; ++i){
        f >> x >> y;
        q[i+n].x = x; q[i+n].y = y; q[i+n].cod = i;
    }
}

inline bool cmp( camp A, camp B ){
    if (A.x == B.x){
        return A.y < B.y;
    }
    return A.x > B.x;
}

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

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

    return S;
}

void bagaUrm(){
    for(int i=1; i<=K; ++i) viz[i] = n+1;
    for(int i=n; i>=1; --i){
        urm[i] = viz[ a[i] ]; viz[ a[i] ] = i;
    }
}

void rezolva(){
    // tin minte pentru fieare i umr[i] = urm aparitie a lui a[i];
    // acum tratez altfel problema : sortez query-urile in ordine descrescatoare dupa capatul stang(un element apare in fata query-ului
    // in caz de egalitate); // si acum raspunsul va fi suma pe 1.. dr; doar ca atunci cand intalnesc un element
    // fac urmatoarele update-uri pe pozitia i pun valoarea a[i] iar pe pozitia urm[i] pun -a[i]; astfel elemente asemenea din interval
    // se anuleaza reciproc si ramane doar unul singur; gen daca am 3 3 3 ; urm e 2 3 4; si eu vin cu astea =>
    //= > i = 3 => aib[] : 0 0 3 -3 i= 2 => aib[] : 0 3 0 ... ramane doar o valoare de 3
    bagaUrm();

    sort(q+1, q+m+n+1, cmp);

    for(int i=1; i<=m+n; ++i){
        if (q[i].cod == 0){// e element
            update( q[i].x, a[ q[i].x ]);
            if (urm[ q[i].x ] != n+1) update( urm[ q[i].x ], -a[ q[i].x ]);// daca urmatoarea aparitie e la n+1 nu ma intereseaza;
        }else {// e query
            rez[ q[i].cod ] = query( q[i].y );
        }
    }

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

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

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

    return 0;
}