#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 100001;
const int MOD = 666013;

pair<pair<int,int>,int> A[N];
int n,m,SOL[N],V[N],AIB[N],P[N],k;

void READ ()
{

    in>>n>>k>>m;

    for( int i=1 ; i <= n ; ++i )
        in>>V[i];

    for( int i=1 ; i <= m ; ++i )
    {

        in>>A[i].first.first>>A[i].first.second;

        A[i].second=i;

    }

}

void UPDATE ( int nod , int val )
{

    if( !nod )
        return ;

    for( ; nod <= n ; nod+=nod&(-nod) )
    {

        AIB[nod]+=val;

        if( AIB[nod] >= MOD )
            AIB[nod]-=MOD;

        if( AIB[nod] < 0 )
            AIB[nod]+=MOD;

    }

}

int QUERY ( int nod )
{

    int S=0;

    for( ; nod ; nod-=nod&(-nod) )
    {

        S+=AIB[nod];

        if( S >= MOD )
            S-=MOD;

        if( S < 0 )
            S+=MOD;

    }

    return S;

}

void SOLVE ()
{

    sort( A+1 , A+m+1 , greater<pair<pair<int,int>,int> >() );

    for( int i=1,j=n ; i <= m ; ++i )
    {

        for( ; j >= A[i].first.first ; --j )
        {

            UPDATE( j , V[j] );
            UPDATE( P[V[j]] , -V[j] );

            P[V[j]]=j;

        }

        SOL[A[i].second]=QUERY(A[i].first.second);

    }

}

void PRINT ()
{

    for( int i=1 ; i <= m ; ++i )
        out<<SOL[i]<<'\n';

}

int main ()
{

    READ ();
    SOLVE ();
    PRINT ();

    return 0;

}