#include <bits/stdc++.h>

using namespace std;

#define N 100004
#define mod 666013

int k,m,n;
int v[N];
int x,y,z;
struct query{
     int x,y,z;
};
int aib[N],sol[N],used[N];
query a[N];
bool cmp(query x,query y){ return y.y > x.y;  }

void add(int x,int y){
    for(;x <=n; x += ( (x ^ (x - 1)) & x )){
        aib[x] += y;
        aib[x] %= mod;
    }
}
int sum(int x){
    int suma=0;
    for(;x;x -= ( (x ^ (x - 1)) & x )){
        suma+=aib[x];
        suma %= mod;
    }
    return suma;
}

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

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

    for(int i=1;i<=n;++i){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d %d",&x,&y);
        a[i] = { x,y,i };
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;++i){
        for(int j= a[i-1].y +1; j <= a[i].y; ++j){
            if( used[ v[j] ] )  add(used[v[j]] , -v[j]);
            add( j ,v[j] );
            used[v[j]] = j;
        }
        sol[a[i].z] = sum( a[i].y ) - sum(a[i].x-1);
        while( sol[a[i].z] < 0 ) sol[a[i].z] += mod;
        sol[a[i].z] %= mod;
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",sol[i]);

    return 0;
}