#include <bits/stdc++.h>

using namespace std;

struct Question {
  int l; int r; int ind;
  bool operator < (const Question &other) {
    return r < other.r;
  }
};

#define ll long long
#define bt(x) x&(-x)

int n;

const int MAXN = 1e5, MOD = 666013;

Question q[MAXN + 1];
int aib[MAXN + 1];
int a[MAXN + 1];
int car[MAXN + 1];
int sol[MAXN + 1];

void update (int poz, int val) {
  while (poz <= n) {
    aib[poz] += val;
    poz += bt (poz);
  }
}

int query (int poz) {
  int sol = 0;
  while (poz) {
    sol += aib[poz];
    poz -= bt (poz);
  }
  return sol;
}

int main() {
  int k, m, i, j, s;
  freopen ("distincte.in", "r", stdin);
  freopen ("distincte.out", "w", stdout);
  scanf ("%d%d%d", &n, &k, &m);
  for (i = 1; i <= n; i++)
    scanf ("%d", &a[i]);
  for (i = 1; i <= m; i++) {
    scanf ("%d%d", &q[i].l, &q[i].r);
    q[i].ind = i;
  }
  sort (q + 1, q + m + 1);
  j = 1; s = 0;
  for (i = 1; i <= m; i++) {
    while (j <= q[i].r) {
      update (j, a[j]);
      s += a[j];
      if (car[a[j]]) {
        update (car[a[j]], -a[j]);
        s -= a[j];
      }
      car[a[j]] = j;
      j++;
    }
    sol[q[i].ind] = (s - query (q[i].l - 1)) % MOD;
  }
  for (i = 1; i <= m; i++)
    printf ("%d\n", sol[i]);
  return 0;
}