#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define MOD 666013
#define Nmax 100100
using namespace std;
int a[Nmax],lst[Nmax], N, M, K;
int AIB[Nmax], ret[Nmax];
int l,r;
pair<pair<int,int>,int> q[Nmax];

inline int zeros(int x) { return x & (-x); }
 
inline void Add(int x, int q) {
    for (int i = x; i <= N; i += zeros(i)) {
      AIB[i] = (AIB[i] + MOD + q) % MOD;
    }
}
inline int comp(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= zeros(i)) {
      ret = (AIB[i] + MOD + ret) % MOD;
    }
    return ret;
}

int main() {
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	//freopen("input.in","r",stdin);
	scanf("%d%d%d",&N,&K,&M);
  for(int i=1;i<=N;++i) {
    scanf("%d",&a[i]);
  }
  for(int i=1;i<=M;++i) {
    scanf("%d%d",&l,&r);
    q[i] = mp(mp(r,l),i);
  }
  sort(q+1,q+M+1);
  for(int i=1;i<=M;++i) {
    l = q[i].fs.sc, r = q[i].fs.fs;
    for(int j=q[i-1].fs.fs+1;j<=r;++j) {
      if(lst[a[j]]) Add(lst[a[j]],-a[j]);
      Add(j,a[j]);
      lst[a[j]] = j;
    }
    ret[q[i].sc] = (comp(r) - comp(l-1) + MOD) % MOD;
  }
  for(int i=1;i<=M;++i) {
    printf("%d\n",ret[i]);
  }
  return 0;
}