#include <fstream>
#include <algorithm>

using namespace std;

const int N_MAX = 100005;
const int MOD = 666013;

int n, m, k;
int v[N_MAX];
int aib[N_MAX];
int ans[N_MAX];
vector<int> oc[N_MAX];
vector<pair<int, int>> qu[N_MAX];

void update(int p, int v) {
  for(; p > 0; p -= (p&-p)) {
    aib[p] += v;
    if(aib[p] >= MOD) {
      aib[p] -= MOD;
    }
  }
}

int query(int p) {
  int q = 0;
  for(; p <= n; p += p&(-p)) {
    q += aib[p];
    if(q >= MOD) {
      q -= MOD;
    }
  }
  return q;
}

int main() {
  ifstream in("distincte.in");
  ofstream out("distincte.out");
  
  in >> n >> k >> m;
  for(int i = 1; i <= n; i++) {
    in >> v[i];
  }
  for(int i = n; i >= 1; i--) {
    oc[v[i]].push_back(i);
  }
  for(int i = 1; i <= m; i++) {
    int a, b;
    in >> a >> b;
    qu[a].emplace_back(b, i);
  }
  for(int i = 1; i <= k; i++) {
    if(!oc[i].empty()) {
      update(oc[i].back(), i);
    }
  }
  for(int i = 1; i <= n; i++) {
    for(auto q : qu[i]) {
      int a = q.first;
      int b = q.second;
      ans[b] = query(i) - query(a + 1);
      oc[v[i]].pop_back();
      if(!oc[v[i]].empty()) {
        update(oc[v[i]].back(), v[i]);
      }
    }
  }
  for(int i = 1; i <= m; i++)
    out << ans[i] << "\n";
  return 0;
}