#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("distincte.in");
ofstream cout ("distincte.out");

const int R = 340;
const int MOD = 666013;

struct Query {
  int x, y, ind;
  bool operator < (const Query &other) const {
    if(x / R == other.x / R)
      return y <= other.y;
    return x < other.x;
  }
} q[100005];

int n, k, m;
int sol;

int ans[100005], v[100005], f[100005];

void update(int poz, int add) {
  if(add > 0) {
    f[v[poz]]++;
    if(f[v[poz]] == 1)
      sol = (sol + v[poz]) % MOD;
  } else {
    f[v[poz]]--;
    if(!f[v[poz]])
      sol = (sol - v[poz] + MOD) % MOD;
  }
}

int main() {
  cin >> n >> k >> m;
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  for(int i = 1; i <= m; i++) {
    cin >> q[i].x >> q[i].y;
    q[i].ind = i;
  }
  sort(q + 1, q + m + 1);
  int l = 1, r = 0;
  for(int i = 1; i <= m; i++) {
    while(q[i].x < l)
      update(--l, 1);
    while(q[i].x > l)
      update(l++, -1);
    while(q[i].y < r)
      update(r--, -1);
    while(q[i].y > r)
      update(++r, 1);
    ans[q[i].ind] = sol;
  }
  for(int i = 1; i <= m; i++)
    cout << ans[i] << "\n";
  return 0;
}