#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define MOD 666013
#define Nadejde 100000
#define Dragoste 4096

typedef struct {
  int l, r, loc, save;
} cell;

int N, M, K, block;
long long int sum;
int val[Nadejde];
int answer[Nadejde];
cell query[Nadejde];
int freq[Nadejde + 1];

/** Parsarea intrarii. **/
int pos = Dragoste;
char c, buff[Dragoste];

/** Da-mi urmatorul caracter din fisier. **/
inline char getChar(FILE *f) {
  if (pos == Dragoste) {
    fread(buff, 1, Dragoste, f);
    pos = 0;
  }
  return buff[pos++];
}

/** Citeste urmatorul numar din fisier. **/
inline int freef(FILE *f) {
  int result = 0;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result;
}

/** Sorteaza intrebarile. **/
void sort(int begin, int end) {
  int b = begin, e = end;
  cell tmp, pivot = query[(b + e) >> 1];

  while (b <= e) {
    while ((query[b].loc < pivot.loc) || ((query[b].loc == pivot.loc) && (query[b].r > pivot.r))) {
      b++;
    }
    while ((query[e].loc > pivot.loc) || ((query[e].loc == pivot.loc) && (query[e].r < pivot.r))) {
      e--;
    }
    if (b <= e) {
      tmp = query[b];
      query[b++] = query[e];
      query[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

/** Adauga elementul val[pos]. **/
inline void insert(int pos) {
  freq[val[pos]]++;
  if (freq[val[pos]] == 1) {
    sum += val[pos];
  }
}

/** Scoate elementul val[pos]. **/
inline void erase(int pos) {
  freq[val[pos]]--;
  if (freq[val[pos]] == 0) {
    sum -= val[pos];
  }
}

int main(void) {
  int i;
  FILE *f = fopen("distincte.in", "r");

  /* Citirea datelor. */
  N = freef(f);
  K = freef(f);
  M = freef(f);
  for (i = 0; i < N; i++) {
    val[i] = freef(f);
  }
  block = sqrt(N);
  for (i = 0; i < M; i++) {
    query[i].l = freef(f);
    query[i].r = freef(f);
    query[i].l--, query[i].r--;
    query[i].loc = query[i].l / block;
    query[i].save = i;
  }
  fclose(f);

  /* Sorteaza intrebarile conform algoritmului lui Mo. */
  sort(0, M - 1);

  /* Respecta rutina de la algoritmul lui Mo. */
  int left = 0, right = -1;
  for (i = 0; i < M; i++) {
    for (; right < query[i].r; insert(++right));
    for (; right > query[i].r; erase(right--));
    for (; left < query[i].l; erase(left++));
    for (; left > query[i].l; insert(--left));
    answer[query[i].save] = sum % MOD;
  }

  /* Afisarea solutiei. */
  freopen("distincte.out", "w", stdout);
  for (i = 0; i < M; i++) {
    fprintf(stdout, "%d\n", answer[i]);
  }
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}