#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define N 100100
#define MOD 666013

using namespace std;

//USING BIT

struct element{
    int x , y ,t, ord ;
};
int n;
element el[2*N];
int arb[N];
int sol[N];
int pr[N];

bool cmp( element a , element b){
    if(a.y != b.y){
        return a.y<b.y;
    }
    return a.t<b.t;
}


void update( int x , int val){
    while( x<=n ){
        arb[x]+=val;
        x= x + ( x & (-x) ) ;
    }
}

int get_sum( int x){
    static int s;

    s=0;
    while(x>0){
        s+=arb[x];
        s = MOD + s%MOD;
        x = x - ( x&(-x) );
    }
    return s;
}


int main(){
    int nrel=0;
    int k, m;
    int i,x ;

    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    scanf("%d %d %d",&n,&k,&m);

    for(i=1 ; i<=n ;i++){
        scanf("%d",&x);
        el[ nrel ].x = x;
        el[ nrel ].y = i;
        el[ nrel++ ].t = 0;

    }

    for(i=0 ; i<m ;i++){
        scanf("%d%d", &el[nrel].x , &el[nrel].y );
        el [nrel].ord =i;
        el[ nrel++ ].t = 1;

    }

    sort(el , el+n+m, cmp);

    memset(pr, -1 , (n+1)* sizeof(int) );

    for(i=0 ; i<n+m ; i++){
        if( el[i].t == 0 ){
            if( pr[ el[i].x ] == -1 ){
                pr [ el[i].x ] = el[i].y ;
                update( el[i].y , el[i].x );
            }else{
                update ( pr[ el[i].x ] , - el[i].x );
                pr [ el[i].x ] = el[i].y ;
                update( el[i].y , el[i].x );
            }
        }else{
            sol[ el[i].ord ] = get_sum( el[i].y ) - ( get_sum( el[i].x - 1 ) ) % MOD ;
        }
    }

    for ( i=0 ;i<m;i++){
        printf("%d\n", sol[i]%MOD);
    }

    return 0;
}