#include<map>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
pair<int,int> qu[101010];
int v[101010];
pair<int,int> rq[101010];
map<pair<int,int>,int> hv;

long long AIB[202020];
int N,M,K;
inline int zeros(int x)
{
return ((x ^ (x - 1)) & x );
}
 
inline void Add(int x, int q)
{
    int i;
 
    for (i = x; i <= N; i += zeros(i))
        AIB[i]+=q;
}
 
inline long long comp(int x)
{
    int i, ret = 0;
 
    for (i = x; i > 0; i -= zeros(i))
        ret = (1LL*ret + AIB[i]) % 666013;
    return ret;
}
inline int comp(int x,int y){
  return (comp(y) - comp(x-1)) % 666013;
}
int cmp(pair<int,int> x,pair<int,int> y){
  return x.sc < y.sc;
}
int start = 1;
int loc[101010];
int move(int x){
  for(;start<=x;++start){
    if(loc[v[start]] != 0){
      Add(loc[v[start]], - v[start]);
    }
    loc[v[start]] = start;
    Add(loc[v[start]], v[start]);
  }
}
int main(){
  freopen("distincte.in","r",stdin);
  freopen("distincte.out","w",stdout);
  scanf("%d%d%d",&N,&K,&M);
  for(int i=1;i<=N;++i){
    scanf("%d",&v[i]);
  }
  for(int i=1;i<=M;++i){
    scanf("%d%d",&qu[i].fs,&qu[i].sc);
    rq[i]=qu[i];
  }
  sort(qu+1,qu+M+1,cmp);
  for(int i=1;i<=M;++i){
    move(qu[i].sc);
    //printf("%d %d\n",qu[i].fs,qu[i].sc);
    hv[qu[i]] = comp(qu[i].fs,qu[i].sc);
  }
  for(int i=1;i<=M;++i){
    printf("%d\n",hv[rq[i]]);
  }

}