#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}

ifstream f("distincte.in");
ofstream g("distincte.out");

const int MOD = 666013;

void add(int &a, int b) {
  a += b;
  if (a >= MOD) a-= MOD;
  if (a < 0) a += MOD;
}

struct BIT {
  vector<int> tree;
  int n;
  BIT(int _n) : n(_n) {
    tree.resize(n + 1, 0);
  }
  inline int lsb(int x) {
    return (x & (-x));
  }
  void update(int pos, int val) {
    while (pos <= n) {
      add(tree[pos], val);
      pos += lsb(pos);
    }
  }
  int query(int pos) {
    int ret = 0;
    while (pos) {
      add(ret, tree[pos]);
      pos -= lsb(pos);
    }
    return ret;
  }
};

struct Query {
  int left, right, idx;
  bool operator<(const Query &other) const {
    return right < other.right;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen(".in", "r", stdin);
#endif

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

  vector<Query> query(m);
  for (int i = 0; i < m; ++i) {
    f >> query[i].left >> query[i].right;
    query[i].idx = i;
  }
  sort(all(query));

  int q = 0;
  vector<int> ans(m);
  vector<int> last_pos(k + 1, 0);
  BIT tree(n);
  for (int i = 1; i <= n; ++i) {
    if (last_pos[v[i]] != 0) {
      tree.update(last_pos[v[i]], -v[i]);
    }
    last_pos[v[i]] = i;
    tree.update(i, v[i]);

    while (q < m && query[q].right == i) {
      ans[query[q].idx] = tree.query(i);
      add(ans[query[q].idx], -tree.query(query[q].left - 1));
      ++q;
    }
  }

  for (int i = 0; i < m; ++i) {
    g << ans[i] << '\n';
  }

  f.close();
  g.close();

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}