#include <bits/stdc++.h>

using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

const int mod = 666013;
const int N = 100002;

void f (int &a) {
  if (a >= mod)
    a -= mod;
}

struct skrr {
  int x, y, i;
} q[N];

bool cmp (skrr a, skrr b) {
  return a.y < b.y;
}
int last[N], aib[N], v[N], ans[N];
int n, k, m;

void update (int x, int val) {
  for (int i = x; i <= n; i += (i & -i)) {
    aib[i] += val;
    f(aib[i]);
  }
}
int query (int x) {
  int sum = 0;
  for (int i = x; i > 0; i -= (i & -i)) {
    sum += aib[i];
    f(sum);
  }
  return sum;
 }

int main()
{
  fin >> n >> k >> m;
  for (int i = 1; i <= n; i++)
    fin >> v[i];
  for (int i = 1; i <= m; i++) {
    fin >> q[i].x >> q[i].y;
    q[i].i = i;
  }
  sort(q + 1, q + m + 1, cmp);
  int p = 1;
  for (int i = 1; i <= n; i++) {
    if (last[v[i]] != 0)
      update(last[v[i]], -v[i]);
    update(i, v[i]);
    last[v[i]] = i;
    int x = query(i);
    while (p <= m && q[p].y == i) {
      ans[q[p].i] = (x - query(q[p].x - 1) + mod) % mod;
      p++;
    }
  }
  for (int i = 1; i <= m; i++)
    fout << ans[i] << "\n";
  return 0;
}