#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

const int BUFFER_SIZE = 4096;
char buffer[BUFFER_SIZE];
int position = BUFFER_SIZE;

inline char getChar( FILE *f )
{
    if ( position == BUFFER_SIZE )
    {
        fread( buffer, 1, BUFFER_SIZE, f );
        position = 0;
    }

    return buffer[ position++ ];
}

inline int read( FILE *f )
{
    int nr = 0;
    char ch;

    do
    {
        ch = getChar( f );

    } while ( !isdigit( ch ) );

    do
    {
        nr = nr * 10 + ( ch - '0' );
        ch = getChar( f );

    } while ( isdigit( ch ) );

    return nr;
}

struct QUERY
{
    int x, y;
    int ind;

    bool operator < ( const QUERY &q ) const
    {
        return y < q.y;
    }
};

const int Nmax = 100000;
const int Qmax = 200000;
const int Vmax = 100000;
const int Pmax =  25000;

int v[Nmax + 1];
int AIB[Nmax + 1];
QUERY queries[Pmax + 1];
int solution[Pmax + 1];
int vis[Vmax + 1];

int N, Q, K;

inline int lsb( int x )
{
    return x & ( -x );
}

void update( int x, int val )
{
    for ( int i = x; i <= N; i += lsb( i ) )
            AIB[i] = ( AIB[i] + val + 666013 ) % 666013;
}

int query( int x )
{
    int s = 0;

    for ( int i = x; i >= 1; i -= lsb( i ) )
            s = ( s + AIB[i] + 666013 ) % 666013;

    return s;
}

int main()
{
    FILE *f = fopen( "distincte.in", "r" );
    FILE *g = fopen( "distincte.out", "w" );

    N = read( f );
    K = read( f );
    Q = read( f );

    for ( int i = 1; i <= N; ++i )
            v[i] = read( f );

    int QQ = 0;

    while ( QQ < Q )
    {
        int limit = min( Pmax, Q - QQ );

        for ( int i = 1; i <= limit; ++i )
        {
            queries[i].x = read( f );
            queries[i].y = read( f );
            queries[i].ind = i;
        }

        QQ += limit;

        sort( queries + 1, queries + limit + 1 );

        for ( int i = 1; i <= limit; ++i )
        {
            for ( int j = queries[i - 1].y + 1; j <= queries[i].y; ++j )
            {
                if ( vis[ v[j] ] )
                        update( vis[ v[j] ], -v[j] );

                vis[ v[j] ] = j;
                update( vis[ v[j] ], v[j] );
            }

            solution[ queries[i].ind ] = ( query( queries[i].y ) - query( queries[i].x - 1 ) + 666013 ) % 666013;
        }

        for ( int i = 1; i <= limit; ++i )
            fprintf(g, "%d\n", solution[i]);

        memset( AIB, 0, sizeof( AIB ) );
        memset( vis, 0, sizeof( vis ) );
    }




    return 0;
}