/*
algoritm:
sortez query-urile crescator dupa capatul dreapta
parcurg apoi query-urile in noua ordine stabilita
folosind vectorul lastPos, adaug in AIB la pozitia j cu -v[j],
daca apare un v[i] = v[j] (cu j < i), iar la pozitia i cu v[i],
astfel valorile care se repeta vor fi anulate
parcurgand query-urile, fiecare element este evaluat o singura data,
iar costul procedurilor din AIB este logaritmic, complexitatea este O(M + NlogN),
iar memoria O(N)

alternativ (85p cu parsare si optimizari) in O(M + NsqrtN) si O(N) memorie
algoritmul lui Mo, impartirea in bucati de cate sqrt(m) a query-urilor
sortarea lor dupa compararea intre cele 2 pozitii de stanga / marimea bucatii
si apoi parcurgerea query-urilor cu 2 indici dupa algoritmul

stanga = 0
dreapta = 0
pentru fiecare query
  fie L stanga din query-ul curent
  fie R dreapta din query-ul curent
  cat timp stanga < L
    sterge(stanga)
    stanga++
   cat timp stanga > L
     stanga--
     adauga(stanga)
   cat timp dreapta <= R
     adauga(dreapta)
     dreapta++
   cat timp dreapta > R + 1
     dreapta--
     sterge(dreapta)
*/

#include <stdio.h>
#include <algorithm>

#define MAX_N 100000
#define NIL -1
#define MOD 666013
#define APPLYMOD(X) ((X) -= (X) / MOD * MOD)

int v[MAX_N];
int lastPos[MAX_N + 1]; // lastPos[i] ultima pozitia a elementului i in urma parcurgerii, initializat cu NIL
int aib[MAX_N];         // aib indexat de la 0
int n;


typedef struct {
  int lo, hi;
  int pos;
} query;

query q[MAX_N];
int ans[MAX_N];

void update(int pos, const int &q) {
  do {
    aib[pos] += q;
    APPLYMOD(aib[pos]);
    pos |= (pos + 1);
  } while (pos < n);
}

int sum(int pos) {
  int q = 0;

  while (pos >= 0) {
    q += aib[pos];
    APPLYMOD(q);
    pos = (pos & (pos + 1)) - 1;
  }

  return q;
}

bool operator <(const query &a, const query &b) {
  if (a.hi == b.hi) {
    return a.lo < b.lo;
  }
  return a.hi < b.hi;
}

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

  fscanf(f, "%d%d%d", &n, &k, &m);
  for (int i = 1; i <= k; i++) {
    lastPos[i] = NIL;
  }
  for (int i = 0; i < n; i++) {
    fscanf(f, "%d", &v[i]);
  }
  for (int i = 0; i < m; i++) {
    fscanf(f, "%d%d", &q[i].lo, &q[i].hi);
    q[i].hi--;    // se va trece in
    q[i].lo--;    // [0, n)
    q[i].pos = i; // retin pozitia, pentru ca vor fi sortate
  }
  fclose(f);

  std::sort(q, q + m);

  pos = 0;
  for (int i = 0; i < m; i++) {
    while (pos <= q[i].hi) {
      if (lastPos[v[pos]] != NIL) {
        update(lastPos[v[pos]], -v[pos]); // anulez fosta valoare
      }
      lastPos[v[pos]] = pos;              // updatez noua valoare
      update(pos, v[pos]);                // si in AIB
      pos++;
    }                                     // la final pos = (q[i].hi + 1), deci nu mai trebuie incrementat pentru urmatoarea iteratie
    ans[q[i].pos] = sum(q[i].hi) - sum(q[i].lo - 1);
    if (ans[q[i].pos] < 0) {              // teorema resturilor
      ans[q[i].pos] = MOD + ans[q[i].pos] % MOD;
    }
  }

  f = fopen("distincte.out", "w");
  for (int i = 0; i < m; i++) {
    fprintf(f, "%d\n", ans[i] % MOD);
  }
  fclose(f);
  return 0;
}