#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], n;
int sol[MAXN];

struct cmp {
  bool operator () ( const query &u, const query &v ) {
    return 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 aib[MAXN];

void update( int pos, int x ) {
  for ( ; pos <= n; pos += pos & -pos ) {
    if ( x < 0 ) {
      submod(aib[pos], -x);
    } else {
      addmod(aib[pos], x);
    }
  }
}

int query( int pos ) {
  int res = 0;
  for ( ; pos > 0; pos -= pos & -pos ) {
    addmod(res, aib[pos]);
  }
  return res;
}

int prv[MAXN];
int lst[MAXN];

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

  fin >> n >> k >> q;
  for ( int i = 1; i <= n; ++i ) {
    fin >> v[i];
    prv[i] = lst[v[i]];
    lst[v[i]] = i;
  }
  for ( int i = 1; i <= q; ++i ) {
    fin >> Q[i].l >> Q[i].r;
    Q[i].idx = i;
  }
  sort( Q + 1, Q + q + 1, cmp() );
  int j = 0;
  for ( int i = 1; i <= q; ++i ) {
    while ( j < Q[i].r ) {
      ++j;
      update( j, v[j] );
      if ( prv[j] ) update( prv[j], -v[j] );
    }
    sol[Q[i].idx] = (query(Q[i].r) - query(Q[i].l - 1) + MOD) % MOD;
  }
  for ( int i = 1; i <= q; ++i ) fout << sol[i] << "\n";
  fin.close();
  fout.close();
  return 0;
}