#include <stdio.h>
#define MAXN 100000
#define MOD 666013
long long p[MAXN + 1], aib[MAXN + 1], v[MAXN];
long long point[MAXN], st[MAXN], dr[MAXN], rez[MAXN];

inline long long ultb(long long x){
  return x & (-x);
}

inline void add(long long p, long long val, long long n){
  if(p <= n){
    aib[p] += val;
    add(p + ultb(p), val, n);
  }
}

inline long long sum(long long p){
  if(p > 0)
    return aib[p] + sum(p - ultb(p));
  return 0;
}

void qs(long long s, long long d){
  long long i = s, j = d, piv = dr[point[(s + d) / 2]], aux;
  while(i <= j){
    while(piv > dr[point[i]])
      i++;
    while(dr[point[j]] > piv)
      j--;
    if(i <= j){
      aux = point[i];  point[i] = point[j];  point[j] = aux;
      i++; j--;
    }
  }
  if(s < j)
    qs(s, j);
  if(i < d)
    qs(i, d);
}

int main(){
  FILE *in = fopen("distincte.in", "r");
  long long n, k, m, i;
  fscanf(in, "%lld%lld%lld", &n, &k, &m);
  for(i = 0; i < n; i++)
    fscanf(in, "%lld", &v[i]);
  for(i = 0; i < m; i++){
    fscanf(in, "%lld%lld", &st[i], &dr[i]);
    point[i] = i;
  }
  fclose(in);
  for(i = 0; i <= k; i++)
    p[i] = -1;
  qs(0, m - 1);
  long long j = 0;
  for(i = 0; i < n; i++){
    if(p[v[i]] != -1)
      add(p[v[i]] + 1, -v[i], n);
    add(i + 1, v[i], n);
    p[v[i]] = i;
    while(j < m && dr[point[j]] == i + 1){
      rez[point[j]] = sum(i + 1) - sum(st[point[j]] - 1);
      j++;
    }
  }
  FILE *out = fopen("distincte.out", "w");
  for(i = 0; i < m; i++){
    fprintf(out, "%lld\n", rez[i] % MOD);
  }
  fclose(out);
  return 0;
}