#include <bits/stdc++.h>
#define usu(x) (x^(x-1))&x
#define mod 666013
using namespace std;
ifstream f ("distincte.in");
ofstream g ("distincte.out");
const int nmax=1e5+3;
int n,k,m,l,v[nmax],aib[nmax],pos[nmax],tir[nmax],p;
struct gioto
{
	int a,b,poz;
	inline bool operator < (const gioto &t) const
	{
	    return b<t.b;
    }
}t[nmax];
void update(int x,int val)
{
	for(;x<=n;x+=usu(x))
    {
        aib[x]=(aib[x]+val)%mod;
        if(aib[x]<0) aib[x]+=mod;
    }
}
int query(int x)
{
	int s=0;
	while(x)
    {
        s=(s+aib[x])%mod;
        x-=usu(x);
    }
	return s;
}
int main()
{
    f>>n>>k>>m;

	for(int i=1;i<=n;++i) f>>v[i];

	for(int i=1;i<=m;++i)
	{
		f>>t[i].a>>t[i].b;
		t[i].poz=i;
	}

	sort(t+1,t+m+1); //sortez jmenos

	p=1;

	for(int i=1;i<=n;++i)
	{
		k=v[i];

		if(pos[k]) update(pos[k],-k); //adaug un nou element

		update(i,k);

		while(p<=m&&t[p].b==i)
		{
			l=t[p].poz;

			tir[l]=query(t[p].b)-query(t[p].a-1); //scad cele care sunt o singura data in spatele lui a

			if(tir[l]<0) tir[l]+=mod;

			++p;
		}
		pos[k]=i;
	}

	for(int i=1;i<=m;++i) g<<tir[i]<<'\n';

    return 0;
}