#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 ll long long
#define MOD 666013
int n, K, M, a[nmax], urm[nmax], viz[nmax];
vector< int > aint[nmax];
vector<int> sum[nmax];

void citeste(){
    f >> n >> K >> M;
    for(int i=1; i<=n; ++i) f >> a[i];
}

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

void faAint(int nod, int st, int dr){
    if (st == dr){
        aint[nod].push_back( st );
        sum[nod].push_back( a[st] );
        return;
    }
    int mij = (st + dr) / 2;
    faAint(nod*2, st, mij);
    faAint(nod*2+1, mij+1, dr);
    // interclasez fii

    aint[nod].clear();
    for(int i=0; i<aint[nod*2].size(); ++i) aint[nod].push_back( aint[nod*2][i] );
    for(int i=0; i<aint[nod*2+1].size(); ++i) aint[nod].push_back( aint[nod*2+1][i] );
    sort(aint[nod].begin(), aint[nod].end(), cmp);
    //acum fac sumele partiale
    sum[nod].clear();
    sum[nod].push_back( a[ aint[nod][0] ] );
    for(int j=1; j<aint[nod].size(); ++j){
        sum[nod].push_back( (sum[nod][j-1] + a[ aint[nod][j] ]) );
    }
}

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

void query(int nod, int st, int dr, int A, int b, int &cnt){
    //cout << nod << "\n";
    if (A <= st && dr <= b){
        //acum vad care dintre y intra; practic am nevoie doar de capatul stang ca eu stiu ca se termina in n+1;
        if (aint[nod].size() == 1){
            int X = aint[nod][0];
            if ( urm[ aint[nod][0] ] > b) cnt += a[X];
            return;
        }
        int newy = cb(-1, aint[nod].size(), nod, b+1);
        //int newy = 0;
        //cout << A << " " << b << " " << newy << " " << nod << " " << aint[nod].size() << "\n";
        int ceva = 0; if (newy > 0) ceva = sum[nod][newy-1];
        ceva = (sum[nod][ aint[nod].size()-1 ] - ceva );
        cnt += ceva;
        return;
    }else {
        int mij = (st + dr) / 2;
        if (A <= mij) query(nod*2, st, mij, A, b, cnt);
        if (b > mij) query(nod*2+1, mij+1, dr, A, b, cnt);
    }
}

void debug(){
    for(int i=1; i<=n; ++i) cout << urm[i] << " ";
    cout << "\n";
}

void rezolva(){
    // problema se poate simplifica daca fiecarui punct ii aflu urmatoare pozitie pe care apare; avand calculat acest lucru
    // o sa am ceva de forma (i, urm[i]); le pun intr-un sistem de coordonate si astfel acum pentru un query (x, y) ma intereseaza
    // elementele ce se afla cu coordoanata x(adica i-ul ) intre x si y iar urmatoarea lor aparitie e intre y+1 si n+1;
    // adica ultima data cand apar elemenetele sunt in afara intervalului x, y;
    // acum ma folosesc de un aint2d in care fiecare nod are intervalul sau st, dr si tine minte suma tututor elementelor cu x-ul intre st, dr
    // fac ceva sume partiale in fiecare nod in aint si atunci pentru un query caut y-ci si aflu suma;
    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;
    }
    //debug();

    faAint(1, 1, n);

    for(int i=1; i<=M; ++i){
        int x, y;f >> x >> y;
        //cout << x << " " << y << "\n";
        int s = 0;
        query(1, 1, n, x, y, s);
        //cout << s << "\n";
        g << s%MOD << "\n";
    }
}

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

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

    return 0;
}