#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 1000005, mod = 666013;
struct meme{
    int a, b, poz;
}q[N];
int v[N], val, n, fr[N], sol[N];
int aib[N];

bool cmp ( meme a, meme b ){
    if ( a.b == b.b )
        return a.a < b.a;
    return a.b < b.b;
}

void update ( int x ){
    while ( x <= n ){
        aib[x] = ( aib[x] + val ) % mod;
        x += ( x & ( - x ) );
    }
}

int quary ( int x ){
    int S = 0;
    while ( x >= 1 ){
        S = ( S + aib[x] ) % mod;
        x -= ( x & ( - x ) );
    }
    return S;
}

int main()
{   int m, p, i, j;
    f >> n >> m >> p;
    for ( i = 1; i <= n; i++ )
        f >> v[i];
    for ( i = 1; i <= p; i++ ){
        f >> q[i].a >> q[i].b;
        q[i].poz = i;
    }
    sort ( q + 1, q + p + 1, cmp );
    int start = 1;
    for ( i = 1; i <= p; i++ ){
        for ( j = start; j <= q[i].b; j++ ){
            if ( fr[v[j]] != 0 ){
                    val = -v[j];
                update ( fr[v[j]] );
            }
            fr[v[j]] = j;
            val = v[j];
            update ( fr[v[j]] );
        }
        start = q[i].b + 1;
        sol[q[i].poz] = quary ( q[i].b ) - quary ( q[i].a - 1 );
        if ( sol[q[i].poz] < 0 )
            sol[q[i].poz] += mod;
    }
    for ( i = 1; i <= p; i++ )
        g << sol[i] << '\n';
    return 0;
}