#include <bits/stdc++.h>
using namespace std;

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

int n ;
struct blabla
{
    int st , dr , ind ;
};

blabla idfk[100001] ;
long long aib[100001] ;

bool cmp ( blabla x , blabla y )
{
    return x.dr < y.dr ;
}

void update ( int poz , int x )
{
    for ( int i = poz ; i <= n ; i += ( i & -i ) )
        aib[i] += x ;

}
long long query ( int poz )
{
    long long s = 0 ;
    for ( int i = poz ; i >= 1 ; i -= ( i & -i ) )
        s += aib[i] ;
    return s ;
}
int v[100001] ;
int fr[100001] ;
long long answer[100001] ;

void solve ()
{
    int m , k;
    fin >> n >> k >> m ;
    for ( int i = 1 ; i <= n ; i ++ )
        fin >> v[i] ;
    int q = m ;
    while ( q )
    {
        fin >> idfk[q].st >> idfk[q].dr ;
        idfk[q].ind = m - q + 1 ;
        q -- ;
    }
    sort ( idfk + 1 , idfk + m + 1 , cmp ) ;
    int qr = 1 ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( fr[v[i]] == 0 )
        {
            fr[v[i]] = i ;
            update ( i , v[i] ) ;
        }
        else
        {
            update ( fr[v[i]] , - v[i] ) ;
            update ( i , v[i] ) ;
            fr[v[i]] = i ;
        }
        long long suma ;
        if ( idfk[qr].dr == i )
            suma = query ( i ) ;
        while ( idfk[qr].dr == i )
        {
            long long sum = query( idfk[qr].st - 1 ) ;
            answer[idfk[qr].ind] = suma - sum ;
            qr ++ ;
        }
    }
    for ( int i = 1 ; i <= m ; i ++ )
        fout << answer[i] % 666013 << '\n' ;
}

signed main()
{
    std :: ios_base :: sync_with_stdio ( false ) ;
    fin.tie ( nullptr ) ;
    fout.tie ( nullptr ) ;
    solve () ;

    return 0;
}