#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in ("distincte.in");
ofstream out ("distincte.out");

#define ll long long

int const nmax = 100000;
int const modulo = 666013;

int v[5 + nmax];

struct Query{
  int x;
  int y;
  int ind;
  bool operator < (Query const &a) const{
    return y < a.y;
  }
};

ll aib[5 + nmax];
int frec[5 + nmax];
int sol[5 + nmax];

void updaib(int x , int n ,int val){
  if(x == 0)
    return ;
  while(x <= n) {
    aib[x] += val;
    x += x ^ (x & (x - 1));
  }
}

ll queryaib(int x ){
  if(x <= 0)
    return 0;

  ll result = 0;
  while(0 < x){
    result += aib[x];
    x = x & (x - 1);
  }
  return result;
}

Query query[5 + nmax];

int main()
{
  int n , k , q;
  in >> n >> k >> q;
  for(int i = 1 ; i <= n ; i++)
    in >> v[i];

  for(int i = 1 ; i <= q ; i++){
    in >> query[i].x >> query[i].y;
    query[i].ind = i;
  }
  sort(query + 1 , query + q + 1);

  int p = 1;

  for(int i = 1 ; i <= q ; i++){

    while(p <= query[i].y){
      updaib(p , n , v[p]);
      if(0 < frec[v[p]] )
        updaib(frec[v[p]] , n , -v[p]);
      frec[v[p]] = p;
      p++;
    }

    sol[query[i].ind] = (queryaib(n) - queryaib(query[i].x - 1)) % modulo;

  }

  for(int i = 1 ;i <= q ; i++)
    out << sol[i] << '\n';

  return 0;
}