#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

bool debug;

void open(){
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
}

void in(int &x){
	char c;
	while (c=getchar()){
		if (c>='0' && c<='9'){
			x=c-'0';
			break;
		}
	}
	while (c=getchar()){
		if (c>='0' && c<='9'){
			x=(x<<1)+(x<<3)+c-'0';
		}
		else break;
	}
}
#define MAXN 100010
#define MOD 666013
struct pii{
	int f,s,z;
	pii(){
	};
	pii(int _f,int _s,int _z){
		f=_f;s=_s;z=_z;
	};
	bool operator<(const pii &X)const{
		if (f!=X.f) return f<X.f;
		return s<X.s;
	};
};
int n,k,m,x[MAXN],a,b,last[MAXN],next[MAXN],tree[MAXN],ans,cur,res[MAXN];
bool used[MAXN],idx[MAXN];
pii p[MAXN];

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

void update(int a,int b){
	for (int i=a;i<MAXN;i+=(i & -i)){
		add(tree[i],b);
	}
}

int query(int a){
	int res=0;
	for (int i=a;i>=1;i-=(i & -i)){
		add(res,tree[i]);
	}
	return res;
}

int main(){
	debug=0;
	if (!debug) open();
	in(n);in(k);in(m);
	for (int i=1;i<=n;i++){
		in(x[i]);
	}
	for (int i=1;i<=k;i++) last[i]=n+1;
	for (int i=n;i>=1;i--){
		next[i]=last[x[i]];
		last[x[i]]=i;
	}
	for (int i=1;i<=n;i++){
		if (!used[x[i]]){
			used[x[i]]=1;
			idx[i]=1;
			update(i,x[i]);
		}
	}
	for (int i=0;i<m;i++){
		in(p[i].f);in(p[i].s);
		p[i].z=i;
	}
	sort(p,p+m);
	cur=1;
	for (int i=0;i<m;i++){
		a=p[i].f;b=p[i].s;
		for (int j=cur;j<a;j++){
			if (idx[j]){
				idx[j]=0;
				used[x[j]]=0;
				update(j,-x[j]);
			}
			if (next[j]<=n){
				idx[next[j]]=1;
				used[x[next[j]]]=1;
				update(next[j],x[next[j]]);
			}
		}
		ans=0;
		add(ans,query(b)-query(a-1)+MOD);
		res[p[i].z]=ans;
		cur=a;
	}
	for (int i=0;i<m;i++) printf("%d\n",res[i]);
	if (debug) system("pause");
	return 0;
}