#include <bits/stdc++.h>

using namespace std;

inline int readNumber()
{
    register int a = 0;
    char ch;

    do
    {
        ch = getchar();

    } while ( !isdigit(ch) );

    do
    {
        a = a * 10 + ch - '0';
        ch = getchar();

    } while ( isdigit(ch) );

    return a;
}

const int Nmax = 100000 + 1;
const int LgMax = 1 + log2(Nmax);
const int MOD = 666013;

struct __attribute__((__packed__)) Node
{
    int L : 17;
    int R : 17;
    int index : 17;
    int sum : 20;
};

Node A[2 * Nmax * LgMax];
int position[Nmax];
int T[Nmax];
int N, M, K, contor;

int mod(int x)
{
    x += MOD;
    return x % MOD;
}

int build( int st, int dr )
{
    if ( st > dr )
        return 0;

    int idx = ++contor;
    int m = ( st + dr ) / 2;

    A[idx] = { build(st, m - 1), build(m + 1, dr), m, 0 };

    return idx;
}

int update( int nod, int new_index, int add )
{
    if ( nod == 0 )
        return 0;

    int idx = ++contor;
    int L = A[nod].L;
    int R = A[nod].R;

    if ( new_index < A[nod].index )
        L = update( L, new_index, add );

    if ( new_index > A[nod].index )
        R = update( R, new_index, add );

    A[idx] = { L, R, A[nod].index, mod(A[nod].sum + add) };

    return idx;
}

int query( int nod, int index )
{
    if ( index < A[nod].index )
        return query( A[nod].L, index ) + mod( A[nod].sum - A[ A[nod].L ].sum );

    if ( index > A[nod].index )
        return query( A[nod].R, index );

    return mod( A[nod].sum - A[ A[nod].L ].sum );
}

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

    ios_base::sync_with_stdio( false );

    N = readNumber(); K = readNumber(); M = readNumber();

    T[0] = build( 1, N );

    for ( int i = 1; i <= N; ++i )
    {
        int val, pos;
        val = readNumber();
        pos = position[val];

        if ( pos == 0  )
            T[i] = update( T[i - 1], i, +val );
        else
        {
            int new_node = update( T[i - 1], pos, -val );
            T[i] = update( new_node, i, +val );
        }

        position[val] = i;
    }

    while ( M-- )
    {
        int a, b;
        a = readNumber(); b = readNumber();

        printf("%d\n", query( T[b], a ) );
    }

    return 0;
}