#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 100005;
const int MOD = 666013;

struct q{
    int start, finish, indice;
};

int n, k, m;
int aib[Nmax];
int v[Nmax], ultima_aparitie[Nmax], ans[Nmax];
q querys[Nmax];

int lsb(int x){
    return (x & (-x));
}

void update(int poz, int val){
    for(int i = poz; i <= n; i += lsb(i)){
        aib[i] = (aib[i] + val + MOD) % MOD;
    }
}

int query(int poz){
    int sol = 0;

    for(int i = poz; i > 0; i -= lsb(i)){
        sol = (sol + aib[i]) % MOD;
    }

    return sol;
}

int query(int lft, int rgt){
    return (query(rgt) - query(lft - 1) + MOD) % MOD;
}

bool cmp(q a, q b){
    if(a.finish == b.finish){
        return a.start < b.start;
    }
    return a.finish < b.finish;
}

int main(){
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");

    int capat_dr;

    fin >> n >> k >> m;

    for(int i = 1; i <= n; i++){
        fin >> v[i];
    }
    for(int i = 1; i <= m; i++){
        fin >> querys[i].start >> querys[i].finish;
        querys[i].indice = i;
    }

    sort(querys + 1, querys + m + 1, cmp);

    capat_dr = 0;
    for(int p = 1; p <= m; p++){
        while(capat_dr < querys[p].finish){
            capat_dr++;

            if(ultima_aparitie[v[capat_dr]]){
                update(ultima_aparitie[v[capat_dr]], -v[capat_dr]);
            }

            ultima_aparitie[v[capat_dr]] = capat_dr;
            update(capat_dr, v[capat_dr]);
        }

        ans[querys[p].indice] = query(querys[p].start, querys[p].finish);
    }

    for(int i = 1; i <= m; i++){
        fout << ans[i] << '\n';
    }

    return 0;
}