#include <fstream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;
const int MOD = 666013;

struct Q {
  int x, y;
  int id;
  bool operator<(const Q& q) {
    return x > q.x;
  }
};

int v[N], ultim[N], aib[N], ans[N], n;
Q q[N];

int zeros(int x) {
  return x & (-x);
}

void update(int val, int poz) {
  while (poz <= n) {
    aib[poz] += val;
    while (aib[poz] >= MOD)
      aib[poz] -= MOD;
    while (aib[poz] < 0)
      aib[poz] += MOD;
    poz += zeros(poz);
  }
}

int query(int poz) {
  int sum = 0;
  while (poz > 0) {
    sum += aib[poz];
    while (sum >= MOD)
      sum -= MOD;
    poz -= zeros(poz);
  }
  return sum;
}

int main() {
  ifstream cin("distincte.in");
  ofstream cout("distincte.out");
  int k, m;
  cin >> n >> k >> m;
  for (int i = 1; i <= n; ++i)
    cin >> v[i];
  for (int i = 0; i < m; ++i) {
    cin >> q[i].x >> q[i].y;
    q[i].id = i;
  }
  cin.close();
  sort(q, q + m);
  int cap_st = n + 1;
  for (int i = 0; i < m; ++i) {
    while (cap_st > q[i].x) {
      --cap_st;
      update(v[cap_st], cap_st);
      if (ultim[v[cap_st]] != 0)
        update(-v[cap_st], ultim[v[cap_st]]);
      ultim[v[cap_st]] = cap_st;
    }
    ans[q[i].id] = query(q[i].y);
  }
  for (int i = 0; i < m; ++i)
    cout << ans[i] << "\n";
  cout.close();
  return 0;
}