#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 100000 //o suta de mii
#define MMAX 100000 //o suta de mii
#define KMAX 100000 //o suta de mii
#define MOD 666013

using namespace std;

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


int N, K, M;
int aib[NMAX + 1];
int v[NMAX + 1];
int raspuns[KMAX + 1];

struct interval{
    int A, B;
    int poz;
}Q[MMAX + 1];

int comparare(interval x, interval y){
    return x.B < y.B;
}

int query(int poz){
    int rsp = 0;
    for(int i = poz; i >= 1; i -= i & (-i)){
        rsp = (rsp + aib[i]) % MOD;
    }
    return rsp;
}

void update(int pos, int val){
    for(int i = pos; i <= N; i += i & (-i)){
        aib[i] = (aib[i] + val) % MOD;
    }
}

int poz[KMAX + 1];
int main()
{
    fin >> N >> K >> M;

    for(int i = 1; i <= N; i++){
        fin >> v[i];
    }

    for(int i = 1; i <= M; i++){
        fin >> Q[i].A >> Q[i].B;
        Q[i].poz = i;
    }

    sort(Q + 1, Q + M + 1, comparare);

    int ultimPoz = 1;
    for(int i = 1; i <= M; i++){

        while(ultimPoz <= Q[i].B){

            if(poz[ v[ultimPoz] ] != 0){ //adica daca a mai aparut
                /*
                    Adica eu daca vreau sa am intervale care se termina in v[i].B, ma intereseaza doar cele mai din dreapta aparitii
                    ale fiecarui numar;

                    vreau ca cea mai din dreapta valoare sa nu fie inclus decat de query-ul eliminat maximal
                    adica sa nu scad aiurea valoarea asta
                */

                update( poz[ v[ultimPoz] ], -v[ ultimPoz ] );
            }

            poz[ v[ultimPoz] ] = ultimPoz;
            update( ultimPoz, v[ultimPoz] );

            ultimPoz++;
        }

        raspuns[ Q[i].poz ] = ( query(Q[i].B) + MOD - query(Q[i].A - 1) ) % MOD; //query-urile nu sunt facute in ordine
        //asa ca salvez rezultatul intr-un vector si afisez rezultatele la final in ordine
    }



    for(int i = 1; i <= M; i++){
        fout << raspuns[i] << "\n";
    }

    return 0;
}