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

#define MAX_N 100000
#define MOD 666013
#define BUFFSIZE (1 << 15)
#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;

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

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);
  }
}

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

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];
int ind[MAX_N];

bool cmp(const int &a, const int &b) {
  int qA = q[a].i / bucket;
  int qB = q[b].i / bucket;

  if (qA == qB) {
    return q[a].j < q[b].j;
  }
  return qA < qB;
}

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 (int i = 0; i < n; i++) {
    v[i] = readInt(f);
  }
  for (int i = 0; i < m; i++) {
    q[i].i = readInt(f) - 1;
    q[i].j = readInt(f) - 1;
    q[i].pos = i;
    ind[i] = i;
  }
  fclose(f);

  std::sort(ind, ind + m, cmp);

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

  for (int i = 0; i < m; i++) {
    int left = q[ind[i]].i;
    int right = q[ind[i]].j;

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