#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define NMax 100000
#define DIM 10000
using namespace std;
char buff[DIM];
int poz;

struct abc{ int x,y,o,res; };
abc q[NMax+1];

const int MOD = 666013;
int aib[NMax+1];
int pos[NMax+1];
int nxt[NMax+1];
int v[NMax+1];
int N;

bool cmp(const abc A, const abc B)
{
    return A.x < B.x;
}

bool cmp2(const abc A, const abc B)
{
    return A.o < B.o;
}

void Read(int& numar)
{
    numar = 0;
    while( !isdigit(buff[poz]) )
    if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    while( isdigit(buff[poz]) )
    {
        numar = numar*10 + buff[poz] - '0';
        if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    }
}

void Update(int p, int x)
{
    while(p <= N)
    {
        aib[p] = ( aib[p] + x + MOD ) % MOD;
        p = p + ( p & (-p) );
    }
}

int Query(int p)
{
    int sum = 0;
    while(p > 0)
    {
        sum = ( sum + aib[p] + MOD ) % MOD;
        p = p - ( p & (-p) );
    }
    return sum;
}

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

    int i,j,x,y,K,M;

    scanf("%d %d %d",&N,&K,&M);
    for(i = 1; i <= N; ++i) Read(v[i]);
    for(i = 1; i <= N; ++i) pos[i] = N+1;
    for(i = N; i >= 1; --i)
    {
        Update(i, v[i]);
        Update(pos[ v[i] ], -v[i]);
        nxt[i] = pos[ v[i] ];
        pos[ v[i] ] = i;
    }

    for(i = 1; i <= M; ++i) { Read(q[i].x); Read(q[i].y); q[i].o = i; }
    sort(q+1,q+M+1,cmp);
    for(K = i = 1; i <= N; ++i)
    {
        while(i==q[K].x) q[K].res = Query(q[K++].y);
        Update(i, -v[i]);
        Update(nxt[i], v[i]);
    }

    sort(q+1,q+M+1,cmp2);
    for(i = 1; i <= M; ++i) printf("%d\n", q[i].res );


return 0;
}