#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MaxT 265000
#define MaxN 100005
#define MaxF 30005
#define MAX 131072
#define MOD 666013
using namespace std;
   
FILE *IN,*OUT;
int pos=0,out=0,sign,N,M,K,last[MaxN],X,Start,End,Pos,Ans;
char f[MAX],Out[MAX],str[10];
int T[MaxT],O[MaxN];
 
struct _Query
{
    int start,end,pos;
}Q[MaxN];
struct _Interval
{
    int val,pos,next;
}v[MaxN];
inline void Write_Ch(char ch)
{
    Out[out++]=ch;
    if(out==MAX)
        fwrite(Out,MAX,1,OUT),out=0;
}
inline void Write_Int(int nr)
{
    int x=0;
    if(nr<0)Write_Ch('-'),nr=-nr;
    do
    {
        str[x++]=nr%10+'0';
        nr/=10;
    }
    while(nr);
    while(x>0)
        Write_Ch(str[--x]);
}
inline int min2(int a,int b)
{
    if (a<b) return a;
    else return b;
}
inline int max2(int a,int b)
{
    if (a>b) return a;
    else return b;
}
inline void Read(int &nr)
{
    sign=0;
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        if(f[pos]=='-')sign=1;
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    if(sign)nr=-nr;
}
  
bool cond(_Interval a,_Interval b)
{
    return a.next<b.next;
}
bool cond2(_Query a,_Query b)
{
    return a.end<b.end;
}
 
void DFS(int node,int start,int end)
{
    if(start==end)
    {
        T[node]=v[start].val;
    }
    else
    {
        int mid=(start+end)>>1;
        DFS(node*2,start,mid);
        DFS(2*node+1,mid+1,end);
        T[node]=(T[node*2]+T[node*2+1])%MOD;
    }
}
void Update(int node,int start,int end)
{
    if(start==end)
        T[node]=0;
    else
    {
        int mid=(start+end)>>1;
        if(Pos>mid)Update(1+2*node,mid+1,end);
        else Update(2*node,start,mid);
        T[node]=(T[2*node+1]+T[2*node])%MOD;
    }
}
void Query(int node,int start,int end)
{
    if(start>=Start&&end<=End)
        Ans=(Ans+T[node])%MOD;
    else
    {
        int mid=(start+end)>>1;
        if(Start<=mid)Query(node*2,start,mid);
        if(End>mid)Query(2*node+1,mid+1,end);
    }
}
int main()
{
    IN=fopen("distincte.in","r");
    OUT=fopen("distincte.out","w");
    fread(f,1,MAX,IN);
    Read(N),Read(K),Read(M);
    for(int i=1;i<=N;i++)
    {
        Read(X);
        v[i].val=X;
        v[i].next=N+1;
        v[i].pos=i;
        v[last[X]].next=i;
        last[X]=i;
    }
    DFS(1,1,N);
    for(int i=1;i<=M;i++)
        Read(Q[i].start),Read(Q[i].end),Q[i].pos=i;
    sort(v+1,v+1+N,cond);
    sort(Q+1,Q+1+M,cond2);
    int j=1;
    for(int i=1;i<=M;i++)
    {
        while(j<=N&&v[j].next<=Q[i].end)
        {
            Pos=v[j].pos;
            j++;
            Update(1,1,N);
        }
        Ans=0;
        Start=Q[i].start,End=Q[i].end;
        Query(1,1,N);
        O[Q[i].pos]=Ans;
    }
    for(int i=1;i<=M;i++)
    {
        Write_Int(O[i]);
        Write_Ch('\n');
    }
    if(out>0)fwrite(Out,1,out,OUT);
    return 0;
}