#include <bits/stdc++.h>
#define L 100005
#define MOD 666013
#define lsb(x) ((x ^ (x - 1)) & x)
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct MS{
  int x;
  int y;
  int i;
  long long ans;
};

int n, k, m;
int v[L], last[L];
MS q[L];
long long aib[L];

bool cmp_y(const MS &a, const MS &b){
  return a.y < b.y;
}

bool cmp_i(const MS &a, const MS &b){
  return a.i < b.i;
}

inline void update(int pos, int val){
  if (pos == 0)
    return;
  for (; pos <= n; pos += lsb(pos))
    aib[pos] += val;
}

inline long long query(int pos){
  long long ret = 0;
  for (; pos > 0; pos -= lsb(pos))
    ret += aib[pos];
  return ret;
}

int main(){
  fin >> n >> k >> m;
  for (int i = 1; i <= n; i++)
    fin >> v[i];
  for (int i = 1; i <= m; i++){
    fin >> q[i].x >> q[i].y;
    q[i].i = i;
  }
  sort(q + 1, q + m + 1, cmp_y);
  int ind = 1;
  for (int i = 1; i <= m; i++){
    while (ind <= q[i].y){
      update(last[v[ind]], -v[ind]);
      update(ind, v[ind]);
      last[v[ind]] = ind;
      ind++;
    }
    q[i].ans = query(q[i].y) - query(q[i].x - 1);
  }
  sort(q + 1, q + m + 1, cmp_i);
  for (int i = 1; i <= m; i++)
    fout << q[i].ans % MOD << "\n";
  return 0;
}