#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400200
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");


int N,M,K,x[NMAX],vec[NMAX],raspuns[NMAX];
vector<int> Poz[NMAX];
pair<pair<int,int>,int> Q[NMAX];

void actualizare(int nod,int st, int dr,int poz,int val)
{
    if (st==dr)
    {
        vec[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
        actualizare(2*nod,st,mij,poz,val);
    else
        actualizare(2*nod+1,mij+1,dr,poz,val);
    vec[nod]=(vec[2*nod]+vec[2*nod+1])%666013;
}
int interogare(int nod,int st,int dr,int inceput,int final)
{
    if (inceput==st && final==dr)
        return vec[nod];
    int mij =(st+dr)/2;
    if (final<=mij)
        return interogare(2*nod,st,mij,inceput,final);
    else if (inceput>mij)
        return interogare(2*nod+1,mij+1,dr,inceput,final);
    else
        return (interogare(2*nod,st,mij,inceput,mij)+interogare(2*nod+1,mij+1,dr,mij+1,final))%666013;
}
void creare(int n)
{
    for (int i=1;i<=n;++i)
        x[i]=i;
}
int main()
{
    int i,q;
    f>>N>>K>>M;
    for (i=1;i<=N;++i)
    {
        f>>x[i];
        Poz[x[i]].push_back(i);
    }
    for (i=1;i<=M;++i)
    {
        f>>Q[i].first.first>>Q[i].first.second;
        Q[i].second=i;
    }
    sort(Q+1,Q+M+1);
    for (i=1;i<=K;++i)
    {
        reverse(Poz[i].begin(),Poz[i].end());
        if (!Poz[i].empty())
            actualizare(1,1,N,Poz[i].back(),i);
    }
    for (q=1,i=1;q<=M;++q)
    {
        for (;i<Q[q].first.first;++i)
        {
            Poz[x[i]].pop_back();
            if (!Poz[x[i]].empty())
              actualizare(1,1,N,Poz[x[i]].back(),x[i]);
        }
        raspuns[Q[q].second]=interogare(1,1,N,Q[q].first.first,Q[q].first.second);
    }
    for (q=1;q<=M;++q)
        g<<raspuns[q]<<"\n";
    return 0;
}