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

using namespace std;

const int Nmax = 100005;
const int modulo = 666013;

struct QUERY
{
    int x;
    int y;
    int ind;

    bool operator < ( const QUERY &b ) const
    {
        return this->y < b.y;
    }

} Q[Nmax];

int N, K, M;
int A[Nmax];
int BIT[Nmax];
int viz[Nmax];
int sol[Nmax];

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

inline int mod( int x )
{
    return ( x + modulo ) % modulo;
}

void update( int poz, int val )
{
    for ( int i = poz; i <= N; i += lsb( i ) )
    {
        BIT[i] = mod( BIT[i] + val );
    }
}

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

    for ( int i = poz; i >= 1; i -= lsb( i ) )
            s = mod( s + BIT[i] );

    return s;
}

int main()
{
    ifstream f("distincte.in");
    ofstream g("distincte.out");

    f >> N >> K >> M;

    for ( int i = 1; i <= N; ++i )
            f >> A[i];

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

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

    for ( int i = 1; i <= M; ++i )
    {
        for ( int j = Q[i - 1].y + 1; j <= Q[i].y; ++j )
        {
            if ( viz[ A[j] ] )
                    update( viz[ A[j] ], -A[j] );

            viz[ A[j] ] = j;
            update( viz[ A[j] ], A[j] );
        }

        sol[ Q[i].ind ] = mod( query( Q[i].y ) - query( Q[i].x - 1 ) );
    }

    for ( int i = 1; i <= M; ++i )
            g << sol[i] << "\n";

    return 0;
}