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

#define MAX_N 100000
#define MOD 666013
#define BUFFSIZE (1 << 20)
#define MAX_DIG 6
#define APPLYMOD(x) ((x) -= (x) / MOD * MOD)

int v[MAX_N];
int cnt[MAX_N + 1];
int ans[MAX_N];

int bucket;

char buffer[BUFFSIZE];
int pos = BUFFSIZE;

char outBuffer[BUFFSIZE];
int outPos;

static inline void put(char c, FILE *f) {
  outBuffer[outPos++] = c;
  if (outPos == BUFFSIZE) {
    fwrite(outBuffer, 1, BUFFSIZE, f);
    outPos = 0;
  }
}

static inline void writeInt(int a, FILE *f) {
  char dig[MAX_DIG];
  int n, q;

  n = 0;
  do {
    q = a / 10;
    dig[n++] = a - (q << 1) - (q << 3) + '0';
    a = q;
  } while (a);

  while (n--) {
    put(dig[n], f);
  }
}

static inline char get(FILE *f) {
  if (pos == BUFFSIZE) {
    fread(buffer, 1, BUFFSIZE, f);
    pos = 0;
  }
  return buffer[pos++];
}

static inline int readInt(FILE *f) {
  int q;
  char c;

  do {
    c = get(f);
  } while (!isdigit(c));

  q = 0;

  do {
    q = (q << 1) + (q << 3) + (c - '0');
    c = get(f);
  } while (isdigit(c));

  return q;
}

typedef struct {
  int i, j;
  int pos;
} query;

query q[MAX_N];

bool operator <(const query &a, const query &b) {
  if (a.i / bucket == b.i / bucket) {
    return a.j < b.j;
  }
  return a.i / bucket < b.i / bucket;
}

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

  n = readInt(f);
  k = readInt(f);
  m = readInt(f);

  bucket = (int) sqrt(n - 1) + 1;
  for (register int i = 0; i < n; i++) {
    v[i] = readInt(f);
  }
  for (register int i = 0; i < m; i++) {
    q[i].i = readInt(f) - 1;
    q[i].j = readInt(f) - 1;
    q[i].pos = i;
  }
  fclose(f);

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

  lo = 0;
  hi = 0;
  sum = 0;

  for (register int i = 0; i < m; i++) {
    while (lo < q[i].i) {
      cnt[v[lo]]--;
      if (!cnt[v[lo]]) {
        sum -= v[lo];
        APPLYMOD(sum);
      }
      lo++;
    }
    while (lo > q[i].i) {
      lo--;
      cnt[v[lo]]++;
      if (cnt[v[lo]] == 1) {
        sum += v[lo];
        APPLYMOD(sum);
      }
    }
    while (hi <= q[i].j) {
      cnt[v[hi]]++;
      if (cnt[v[hi]] == 1) {
        sum += v[hi];
        APPLYMOD(sum);
      }
      hi++;
    }
    while (hi > q[i].j + 1) {
      hi--;
      cnt[v[hi]]--;
      if (!cnt[v[hi]]) {
        sum -= v[hi];
        APPLYMOD(sum);
      }
    }
    while (sum < 0) {
      sum += MOD;
    }
    ans[q[i].pos] = sum;
  }
  f = fopen("distincte.out", "w");
  for (register int i = 0; i < m; i++) {
    writeInt(ans[i], f);
    put('\n', f);
  }
  fwrite(outBuffer, 1, outPos, f);
  fclose(f);
  return 0;
}