#include<fstream>
#include<algorithm>
#define MOD 666013
#define Nmax 100100

using namespace std;

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

int N, M, K, A[Nmax], u[Nmax];
int AIB[Nmax], sol[Nmax];
int Left, Right;
pair<pair<int, int>, int> q[Nmax];

void update(int idx, int val)
{
    while(idx <= N)
    {
        AIB[idx] = (AIB[idx]+MOD+val)%MOD;
        idx += idx & -idx;
    }
}

int query(int idx)
{
    int sum=0;
    while(idx > 0)
    {
        sum = (AIB[idx]+MOD+sum)% MOD;
        idx -= idx & -idx;
    }
    return sum;
}

int main()
{
    fin>>N>>K>>M;
    for(int i=1; i<=N; ++i)
    {
        fin>>A[i];
    }
    for(int i=1; i<=M; ++i)
    {
        fin>>Left>>Right;
        q[i] = make_pair(make_pair(Right,Left),i);
    }
    sort(q+1,q+M+1);
    for(int i=1; i<=M; ++i)
    {
        Left=q[i].first.second;
        Right=q[i].first.first;
        for(int j=q[i-1].first.first+1; j<=Right; ++j)
        {
            if(u[A[j]])
                update(u[A[j]], -A[j]);
            update(j, A[j]);
            u[A[j]] = j;
        }
        sol[q[i].second] = (query(Right) - query(Left-1) + MOD) % MOD;
    }
    for(int i=1; i<=M; ++i)
    {
        fout<<sol[i]<<'\n';
    }
    return 0;
}