#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int MAXN = 100005;
const int MOD = 666013;

struct query {
  int l, r, idx;
} Q[MAXN];

int v[MAXN], freq[MAXN];
int sol[MAXN];
int R;

struct cmp {
  bool operator () ( const query &u, const query &v ) {
    return (u.l / R < v.l / R) || (u.l / R == v.l / R && u.r > v.r);
  }
};

inline void addmod( int &res, int x ) {
  res += x;
  if ( res >= MOD ) res -= MOD;
}
inline void submod( int &res, int x ) {
  res -= x;
  if ( res < 0 ) res += MOD;
}

int main() {
  int n, k, q, res = 0;

  fin >> n >> k >> q;
  for ( int i = 1; i <= n; ++i ) {
    fin >> v[i];
  }
  for ( int i = 1; i <= q; ++i ) {
    fin >> Q[i].l >> Q[i].r;
    Q[i].idx = i;
  }
  R = sqrt((long long)n * n / q);
  sort(Q + 1, Q + q + 1, cmp());
  int l = Q[1].l, r = Q[1].r;
  for ( int i = l; i <= r; ++i ) {
    ++freq[v[i]];
    if ( freq[v[i]] == 1 ) addmod(res, v[i]);
  }
  sol[Q[1].idx] = res;
  for ( int i = 2; i <= q; ++i ) {
    while ( l > Q[i].l ) {
      --l;
      ++freq[v[l]];
      if ( freq[v[l]] == 1 ) addmod(res, v[l]);
    }
    while ( Q[i].r > r ) {
      ++r;
      ++freq[v[r]];
      if ( freq[v[r]] == 1 ) addmod(res, v[r]);
    }
    while ( l < Q[i].l ) {
      --freq[v[l]];
      if ( freq[v[l]] == 0 ) submod(res, v[l]);
      ++l;
    }
    while ( Q[i].r < r ) {
      --freq[v[r]];
      if ( freq[v[r]] == 0 ) submod(res, v[r]);
      --r;
    }
    sol[Q[i].idx] = res;
  }
  for ( int i = 1; i <= q; ++i ) fout << sol[i] << "\n";
  fin.close();
  fout.close();
  return 0;
}