#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;

}