#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int M = 666013;

int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b %  M;
}

const int N = (int) 1e5 + 7;
int n, k, q, t[N], sol[N], a[N];
vector<int> p[N];
vector<pair<int, int>> memo[N];

void __add(int i, int x) {
  while (i <= n) {
    t[i] = add(t[i], x);
    i += i & (-i);
  }
}

int pre(int i) {
  int sol = 0;
  while (i) {
    sol = add(sol, t[i]);
    i -= i & (-i);
  }
  return sol;
}

int main() {
  freopen ("distincte.in", "r", stdin);
  freopen ("distincte.out", "w", stdout);
  scanf("%d %d %d", &n, &k, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    p[a[i]].push_back(i);
  }
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    memo[l].push_back({r, i});
  }
  for (int x = 1; x <= k; x++) {
    reverse(p[x].begin(), p[x].end());
    if (!p[x].empty()) {
      __add(p[x].back(), x);
    }
  }
  for (int l = 1; l <= n; l++) {
    for (auto &it : memo[l]) {
      int r = it.first, i = it.second;
      sol[i] = pre(r);
    }
    __add(p[a[l]].back(), -a[l]);
    p[a[l]].pop_back();
    if (!p[a[l]].empty()) {
      __add(p[a[l]].back(), a[l]);
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", sol[i]);
  }
  return 0;
}