#include <iostream>
#include <fstream>
#include <vector>

#define MAXN 100001
#define MODULO 666013

int v[100001];
std::vector<int> merged[3 * MAXN + 1];

void merge(std::vector<int>& dest, std::vector<int>& a, std::vector<int>& b) {
  int ia = 0;
  int ib = 0;
  while (ia < a.size() && ib < b.size()) {
    if (a[ia] == b[ib]) {
      dest.push_back(a[ia]);
      ia++;
      ib++;
    } else if (a[ia] < b[ib]) {
      dest.push_back(a[ia]);
      ia++;
    } else {
      dest.push_back(b[ib]);
      ib++;
    }
  }

  while (ia < a.size()) {
    dest.push_back(a[ia]);
    ia++;
  }

  while (ib < b.size()) {
    dest.push_back(b[ib]);
    ib++;
  }
}

inline int get_sum(std::vector<int>& v) {
  long long sol = 0;
  for (int i = 0; i < v.size(); ++i) {
    sol += v[i];
  }

  return sol % MODULO;
}

void get_merge(int node, int li, int lf) {
  if (li > lf) {
    return;
  }

  if (li == lf) {
    merged[node].push_back(v[li]);
    return;
  }

  get_merge(node * 2, li, (li + lf) / 2);
  get_merge(node * 2 + 1, (li + lf) / 2 + 1, lf);
  merge(merged[node], merged[node * 2], merged[node * 2 + 1]);
}

void get_dist(int node, int li, int lf, int a, int b, std::vector<int>& solm) {
  // Doesn't intersect at all.
  if (b < li || a > lf) {
    return;
  }

  // Completely included.
  if (a <= li && b >= lf) {
    std::vector<int> tomerge;
    merge(tomerge, solm, merged[node]);
    solm.swap(tomerge);
    return;
  }

  // Not included.
  get_dist(node * 2, li, (li + lf) / 2, a, b, solm);
  get_dist(node * 2 + 1, (li + lf) / 2 + 1, lf, a, b, solm);
}

int main() {
  std::ifstream in("distincte.in");
  std::ofstream out("distincte.out");

  int n, k, m;
  in >> n >> k >> m;
  for (int i = 0; i < n; ++i) {
    in >> v[i];
  }

  get_merge(1, 0, n - 1);

  for (int i = 0; i < m; ++i) {
    int a, b;
    in >> a >> b;
    std::vector<int> solm;
    get_dist(1, 0, n - 1, a - 1, b - 1, solm);
    out << get_sum(solm) << std::endl;
  }

  in.close();
  out.close();

  return 0;
}