#include <cstdio>
#include <algorithm>

using namespace std;

const int MOD=666013;

int f[100001], l[100001], nxt[100001], v[100001], r[100001], aib[100001];
int n;

struct date
{
    int st, dr, poz;
} query[100000];

void update( int p, int val )
{
    for( ; p!=0 && p<=n; p+=p&-p )
        aib[p]=(aib[p]+val)%MOD;
}

int qrry( int p )
{
    int s=0;

    for( ; p>0; p-=p&-p )
        s=s+aib[p];

    return s;
}

int sol( int a, int b )
{
    return (MOD+qrry(b)-qrry(a-1))%MOD;
}

bool cmp( date a, date b )
{
    if( a.st<b.st )
        return 1;

    return 0;
}

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

    int q, k, x, i, j;

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

    for( i=1;i<=n;i++ )
    {
        scanf( "%d", &v[i] );

        if( f[v[i]]==0 )
            f[v[i]]=l[v[i]]=i;
        else
            l[v[i]]=nxt[l[v[i]]]=i;
    }

    for( i=0;i<q;i++ )
    {
        scanf( "%d%d", &query[i].st, &query[i].dr );
        query[i].poz=i;
    }

    sort(query,query+q,cmp);

    for( i=1;i<=k;i++)
        update(f[i],i);

    j=0;

    for( i=1;i<=n;i++ )
    {
        while( j<q && i==query[j].st )
        {
            r[query[j].poz]=sol(query[j].st,query[j].dr);
            j++;
        }
        update(nxt[i],v[i]);
    }

    for( i=0;i<q;i++ )
        printf( "%d\n", r[i] );

    return 0;
}