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

long long AIB[102020];
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;
    long long ret = 0; 
    for (i = x; i > 0; i -= zeros(i))
        ret = ret + AIB[i];
    return ret;
}
inline int comp(int x,int y){
  return (comp(y) - comp(x-1)) % 666013;
}
int cmp(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y){
  return x.fs.sc < y.fs.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 rez[101010];
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.fs,&qu[i].fs.sc);
    qu[i].sc=i;
 }
  sort(qu+1,qu+M+1,cmp);
  for(int i=1;i<=M;++i){
    move(qu[i].fs.sc);
    rez[qu[i].sc] = comp(qu[i].fs.fs,qu[i].fs.sc);
  }
  for(int i=1;i<=M;++i){
    printf("%d\n",rez[i]);
  }

}