#include <fstream>
#include <algorithm>

using namespace std;

const int MAXN = 100001;
const int MOD = 666013;

struct Query {
  int l, r, pos;
} q[MAXN + 1];

int cmp(Query A, Query B) {
  return A.r < B.r;
}

inline int zero(int x) {
  return x & -x;
}

int aib[MAXN], last[MAXN], ans[MAXN], v[MAXN], n;

inline void update(int pos, int val) {
  if (pos == 0)
    return;
  for (int i = pos; i <= n; i += zero(i))
    aib[i] = (aib[i] + val + MOD) % MOD;
}

inline int query(int pos) {
  int ans = 0;
  for (int i = pos; i > 0; i -= zero(i))
    ans = (ans + aib[i]) % MOD;
  return ans;
}

int main()
{
    ifstream fin("distincte.in");
    int k, m, i, j;
    fin >> n >> k >> m;
    for (i = 1; i <= n; ++i)
      fin >> v[i];
    for (i = 0; i < m; ++i) {
      fin >> q[i].l >> q[i].r;
      q[i].pos = i;
    }
    fin.close();
    sort(q, q + m, cmp);
    for (i = 1, j = 0; i <= n; ++i) {
      update(i, v[i]); update(last[v[i]], -v[i]); last[v[i]] = i;
      while (q[j].r == i) {
        ans[q[j].pos] = (query(q[j].r) - query(q[j].l - 1) + MOD) % MOD;
        ++j;
      }
    }
    ofstream fout("distincte.out");
    for (i = 0; i < m; ++i)
      fout << ans[i] << '\n';
    fout.close();
    return 0;
}