#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;

int v[Nmax + 1];
int AIB[Nmax + 1];
QUERY queries[Qmax + 1];
int solution[Qmax + 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 );

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

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

    for ( int i = 1; i <= Q; ++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 <= Q; ++i )
            fprintf(g, "%d\n", solution[i]);

    return 0;
}