#include <cstdio>
#include <algorithm>

#define terminal0(x) x & -x

const int MAX_N = 100000;
const int MAX_M = 100000;
const int MOD = 666013;

struct Query {
  int left;
  int right;
  int index;
  
  bool operator <(const Query &other) const {
    return this->right < other.right;
  }
};

int n;
int aib[1 + MAX_N];
int v[1 + MAX_N];
int last[1 + MAX_N];
Query queries[1 + MAX_M];
int ans[1 + MAX_M];

void update(int poz, int val) {
  for (int i = poz; i <= n; i += terminal0(i))
    aib[i] = (aib[i] + val) % MOD;
}

int query(int poz) {
  int ans = 0;
  for (int i = poz; i >= 1; i -= terminal0(i))
    ans = (ans + aib[i]) % MOD;
  return ans;
}

int main() {
  freopen("distincte.in", "r", stdin);
  freopen("distincte.out", "w", stdout);
  
  int k, m;
  scanf("%d%d%d", &n, &k, &m);
  for (int i = 1; i <= n; i++)
    scanf("%d", &v[i]);
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    queries[i] = {l, r, i};
  }
  std::sort(queries + 1, queries + m + 1);
  int poz = 1;
  for (int i = 1; i <= n; i++) {
    update(i, v[i]);
    if (last[v[i]] != 0)
      update(last[v[i]], -v[i]);
    last[v[i]] = i;
    while (poz <= m && queries[poz].right == i) {
      ans[queries[poz].index] = (MOD + query(i) - query(queries[poz].left - 1)) % MOD;
      poz++;
    }
  }
  for (int i = 1; i <= m; i++)
    printf("%d\n", ans[i]);
  return 0;
}