#include <bits/stdc++.h>

using namespace std;

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()
{
    cout << sizeof( A ) / 1024.0 / 1024.0 << endl;

    ifstream in("distincte.in");
    ofstream out("distincte.out");

    ios_base::sync_with_stdio( false );

    in >> N >> K >> M;

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

    for ( int i = 1; i <= N; ++i )
    {
        int val, pos;
        in >> val;
        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;
        in >> a >> b;

        out << query(T[b], a) << "\n";
    }

    return 0;
}