#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 100003
#define MOD 666013

#define ff first
#define ss second
#define MP make_pair

/*
x = (x + val) % MOD
x = (x - val + MOD) % MOD
*/

int n, k, m;
int a[NMAX];
int tree[3*NMAX];
int urm[NMAX];
pair< pair<int, int>, int> q[NMAX];
int res[NMAX];

#define mid(st, dr) (((st)+(dr)) >> 1)
#define left(i) ((i) << 1)
#define right(i) (((i) << 1)+1)

void update(int n, int st, int dr, int x, int val)
{
	if(st == dr)
	{
		tree[n] = val;
		return ;
	}
	int m = mid(st, dr);
	
	if(x <= m)
		update(left(n), st, m, x, val);
	else
		update(right(n), m+1, dr, x, val);
	
	tree[n] = (tree[left(n)] + tree[right(n)]) % MOD;
}

int query(int n, int st, int dr, int x, int y)
{
	if(x <= st && dr <= y)
		return tree[n];
		
	int m = mid(st, dr);
	
	int res1 = 0, res2 = 0;
	if(x <= m)
		res1 = query(left(n), st, m, x, y);
	if(y > m)
		res2 = query(right(n), m+1, dr, x, y);
		
	return (res1 + res2) % MOD;
}

void read()
{
	pair< pair<int, int>, int> aux;
	scanf("%d %d %d", &n, &k, &m);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d ", &a[i]);
		update(1, 1, n, i, a[i]);
	}
	for(int i = 1; i <= m; ++i)	scanf("%d %d\n", &q[i].ff.ff, &q[i].ff.ss), q[i].ss = i;	
}

void compute_urm()
{
	int last[NMAX];
	memset(last, -1, sizeof(last));
	for(int i = 1; i <= n; ++i)
	{
		urm[i] = last[ a[i] ];
		last[ a[i] ] = i;
	}
}

int f(pair< pair<int, int>, int> a, pair< pair<int, int>, int > b)
{
	if(a.ff.ss < b.ff.ss) return 1;
	if(a.ff.ff < b.ff.ff) return 1;
	return 0;
}



int main()
{
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);

	read();

	compute_urm();

	sort(q+1, q+m+1, f);

	/*
	for(int i = 1; i <= m; ++i)
		printf("%d: %d %d\n", q[i].ss, q[i].ff.ff, q[i].ff.ss);
	for(int i = 1; i <= n; ++i)
		printf("%d ", urm[i]);
	*/
	int counter = 0;
	for(int i = 1; i <= m; ++i)
	{
		int x, y, z;
		x = q[i].ff.ff;
		y = q[i].ff.ss;
		z = q[i].ss;
		
		for(; counter <= y; )
		{
			if(urm[counter] != -1)
				update(1, 1, n, urm[counter], 0);
			++counter;
		}
		res[z] = query(1, 1, n, x, y);
	} 
	for(int i = 1; i <= m; ++i)
		printf("%d\n", res[i]);
	
	return 0;
}