#include <fstream>
#include <algorithm>

using namespace std;

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

struct que {
  int st, dr, poz, rez;
};

const int N = 100005, MOD = 666013;

que a[N];

int n, k, q, v[N], aib[N], lpoz[N];

void read() {
  in>>n>>k>>q;  
  for (int i = 1; i <= n; ++i)
    in>>v[i];
  for (int i = 1; i <= q; ++i) {
    in>>a[i].st>>a[i].dr;
    a[i].poz = i;
  }
}

bool comp(const que &a, const que &b) {
  return a.dr < b.dr;
}

void init() {
  sort(a + 1, a + q + 1, comp);
}

inline int bit(int x) {
  return (x & (- x));
}

void mod(int &a) {
  if (a < 0)
    a += MOD;
  if (a >= MOD)
    a -= MOD;
}

void update(int poz, int val) {
  if (! poz)
    return;
  while (poz <= n) {
    aib[poz] += val;
    mod(aib[poz]);
    poz += bit(poz);
  }
}

int query(int poz) {
  int rez = 0;
  while (poz > 0) {
    rez += aib[poz];
    mod(rez);
    poz -= bit(poz);
  }
  return rez;
}

void solve() {
  int lastn = 0, rst = 0, rdr = 0;
  for (int i = 1; i <= q; ++i) {
    while (lastn + 1 <= a[i].dr){
      lastn++;
      update(lpoz[v[lastn]], - v[lastn]);
      lpoz[v[lastn]] = lastn;
      update(lastn, v[lastn]);
    }
    rdr = query(a[i].dr);
    rst = query(a[i].st - 1);
    a[i].rez = rdr - rst;
    mod(a[i].rez);
  }
}

bool comp2(const que &a, const que &b) {
  return a.poz < b.poz;
}

void afis() {
  sort(a + 1, a + q + 1, comp2);
  for (int i = 1; i <= q; ++i)
    out<<a[i].rez<<"\n";
}

int main() {
  read();
  init();
  solve();
  afis();
  return 0;
}