#include <bits/stdc++.h>

using namespace std;

struct Query {
  int x, y, i;
}q[100005];

bool cmp(Query a, Query b) {
  return a.x < b.x;
}

int sol[100005];
int val[100005];
int v[100005];
vector<int>G[100005];
long long aib[100005];

void u(int poz, int n, int val) {
  for (; poz <= n; poz += (poz & -poz))
    aib[poz] += val;
}

long long qr(int poz) {
  long long ans = 0;
  for (; poz; poz -= (poz & -poz))
    ans += aib[poz];
  return ans;
}

int main() {
  freopen("distincte.in", "r", stdin);
  freopen("distincte.out", "w", stdout);

  int n, k, m;
  scanf("%d%d%d", &n, &k, &m);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    v[i] = x;
    if (G[x].size() == 0)
      u(i, n, x);
    G[x].push_back(i);
  }

  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &q[i].x, &q[i].y);
    q[i].i = i;
  }

  sort(q + 1, q + m + 1, cmp);


  int i = 1;
  for (int j = 1; j <= m; ++j) {
    while (i <= n && i < q[j].x) {
      u(i, n, -v[i]);
      val[v[i]]++;
      if (val[v[i]] != G[v[i]].size())
        u(G[v[i]][val[v[i]]], n, v[i]);
      i++;
    }
    sol[q[j].i] = 1LL * qr(q[j].y) % 666013;
  }

  for (int i = 1; i <= m; ++i)
    printf("%d\n", sol[i]);

  return 0;
}