#include<bits/stdc++.h>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const long long N = 100005;
const long long MOD = 666013;
struct Query
{
    long long st, dr, poz;
};
long long aint[N*4],n,m,k,poz[N],v[N];
Query q[N];
void citire()
{
    in>>n>>k>>m;
    for ( long long i = 1 ; i <= n ; i++ )
    {
        in>>v[i];
    }
    for ( long long i = 1 ; i <= m ; i++ )
    {
        in>>q[i].st>>q[i].dr;
        q[i].poz = i;
    }
}
long long fs(long long nod) { return nod * 2; }
long long fd(long long nod) { return nod * 2 + 1; }
void update_interval(long long nod, long long st, long long dr, long long qs, long long qd, long long val)
{
    if ( qs <= st && dr <= qd )
    {
        aint[nod] += val;
        return;
    }
    if ( st > qd || qs > dr )
    {
        return;
    }
    long long mij = ( st + dr ) / 2;
    if ( qs <= mij )
        update_interval(fs(nod), st, mij, qs, qd, val);
    if ( mij < qd )
        update_interval(fd(nod), mij + 1, dr, qs, qd, val);
}
long long query_poz(long long nod, long long st, long long dr, long long poz)
{
    if ( st == dr )
    {
        return aint[nod];
    }
    long long mij = ( st + dr ) / 2;
    if ( poz <= mij )
        return query_poz(fs(nod), st, mij, poz) + aint[nod];
    return query_poz(fd(nod), mij + 1, dr, poz) + aint[nod];
}
long long query(long long st, long long dr)
{
    long long aux;
    if ( st == 1 )
        aux = 0;
    else
        aux = query_poz(1, 1, n, st - 1);
    return query_poz(1, 1, n, dr) - aux;
}
bool cmp(Query a, Query b)
{
    return a.dr < b.dr;
}
void rez()
{
    sort ( q + 1, q + m + 1 , cmp );
    long long dr = 1;
    vector<int> ans(m+1);
    for ( long long i = 1 ; i <= m ; i++ )
    {
        while ( dr <= q[i].dr )
        {
            if ( poz[v[dr]] )
            {
                update_interval(1, 1, n, poz[v[dr]], n, -v[dr]);
            }
            poz[v[dr]] = dr;
            update_interval(1, 1, n, dr, n, v[dr]);
            dr++;
        }
        ans[q[i].poz] = query(q[i].st, q[i].dr)%MOD;
    }
    for ( long long i = 1 ; i <= m ; i++ )
    {
        out<<ans[i]%MOD<<'\n';
    }
}
int main()
{
    citire();
    rez();
    return 0;
}