#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 100002
#define Mod 666013
#define LSB(x) ( (x) & -(x) )

FILE *f = fopen ( "distincte.in", "r" );
FILE *g = fopen ( "distincte.out", "w" );

int N, K, M;
int v[Nmax], AIB[Nmax], Last[Nmax], indQ[Nmax], sol[Nmax];

struct interv{
    int st, dr;
}Qry[Nmax];

void Update ( int poz, int val ){

    for ( int i = poz; i <= N; i += LSB(i) )
        AIB[i] += val;
}

int Query ( int poz ){

    int sum = 0;

    for ( int i = poz; i >= 1; i -= LSB(i) )
        sum += AIB[i];

    return sum;
}

int Suma ( int st, int dr ){
    return Query ( dr ) - Query ( st-1 );
}

bool cmp ( int A, int B ){
    return Qry[A].dr < Qry[B].dr;
}

int main(){

    fscanf ( f, "%d%d%d", &N, &K, &M );

    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d", &v[i] );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d", &Qry[i].st, &Qry[i].dr );
        indQ[i] = i;
    }

    sort ( indQ + 1, indQ + M + 1, cmp );

    int lastdr = 0;

    for ( int i = 1; i <= M; ++i ){
        for ( int j = lastdr+1; j <= Qry[indQ[i]].dr; ++j ){
            if ( Last[v[j]] != 0 )
                Update ( Last[v[j]], -v[j] );
            Update ( j, v[j] );
            Last[v[j]] = j;
        }
        sol[indQ[i]] = Suma ( Qry[indQ[i]].st, Qry[indQ[i]].dr );
        lastdr = Qry[indQ[i]].dr;
    }

    for ( int i = 1; i <= M; ++i )
        fprintf ( g, "%d\n", sol[i] % Mod );

    return 0;
}