#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e5 + 5;
const int mod = 666013;

struct data{
  int x, y, u;
}a[kN];

int v[kN], f[kN], ans[kN];
int n, k, q, sum, blockSize;

bool cmp (data a, data b){
  return make_pair(a.x / blockSize, a.y) < make_pair(b.x / blockSize, b.y);
}

void update (int poz){
  int e = v[poz];
  if (f[e] == 0){
    sum += e;
  }
  f[e] += 1;
}

void del (int poz){
  int e = v[poz];
  if (f[e] == 1){
    sum -= e;
  }
  f[e] -= 1;
}

int main(){
  fin >> n >> k >> q;
  blockSize = (int)n / sqrt(n);
  for (int i = 1; i <= n; i++){
    fin >> v[i];
  }
  for (int i = 1; i <= q; i++){
    fin >> a[i].x >> a[i].y;
    a[i].u = i;
  }

  sort(a + 1, a + q + 1, cmp);
  int cur_l = 1, cur_r = 0;
  for (int i = 1; i <= q; i++){
    int l = a[i].x, r = a[i].y;
    while (cur_l > l){
      cur_l -= 1;
      update(cur_l);
    }
    while (cur_r < r){
      cur_r += 1;
      update(cur_r);
    }
    while (cur_l < l){
      del(cur_l);
      cur_l += 1;
    }
    while (cur_r > r){
      del(cur_r);
      cur_r -= 1;
    }
    ans[a[i].u] = sum;
  }
  for (int i = 1; i <= q; i++){
    fout << ans[i] % mod << "\n";
  }
}