#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define NMAX 100010
#define MOD 666013
#define ubit(x) ( ((x) & ((x) - 1)) ^ (x))
#define nd(a) (*(t_v *)(a))

typedef struct t_v
{
	int x, y;
     int ind;
};

int cmp(const void *a, const void *b);
void read();
void update(int poz, int x);
int query(int poz);
void easy();

int N, M, K, A[NMAX], v[NMAX], sol[NMAX], seen[NMAX];
t_v V[NMAX], Q[NMAX];

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

     read();
	return 0;
}

void read()
{
	int i, a, b, j;
     
	scanf("%d%d%d", &N, &K, &M);

	for(i = 1; i <= N; i++)
     {
     	scanf("%d", &V[i].x);
          v[i] = V[i].x;
          update(i, V[i].x);
          V[i].y = i;
     }
     qsort(V + 1, N, sizeof(t_v), cmp);

     for(i = 1; i <= N; i++)
     {
		if(V[i + 1].x != V[i].x) V[i].x = N + 1;
          else V[i].x = V[i + 1].y;
     }
     qsort(V + 1, N, sizeof(t_v), cmp);
     for(i = 0; i < M; i++)
     {
     	scanf("%d%d", &a, &b);
          Q[i].x = b, Q[i].y = a;
          Q[i].ind = i;
     }
     //easy();
     freopen("distincte.out", "w", stdout);
     qsort(Q, M, sizeof(t_v), cmp);
     for(i = 0, j = 1; i < M; i++)
     {
		for(; V[j].x <= Q[i].x && j <= N; j++)
          update(V[j].y, -v[V[j].y]);
          sol[Q[i].ind] = (query(Q[i].x) - query(Q[i].y - 1) + MOD) % MOD;
     }
     for(i = 0; i < M; i++)
     printf("%d\n", sol[i]);
}

int cmp(const void *a, const void *b)
{
	if(nd(a).x != nd(b).x)
     return nd(a).x - nd(b).x;
     return nd(a).y - nd(b).y;
}

void update(int poz, int x)
{
	if(x >= 0)
	for(; poz <= N; poz += ubit(poz))
     A[poz] += x, A[poz] = A[poz] >= MOD ? A[poz] - MOD : A[poz];
     else
     for(; poz <= N; poz += ubit(poz))
     A[poz] += x + MOD, A[poz] = A[poz] >= MOD ? A[poz] - MOD : A[poz];
}

int query(int poz)
{
	int rez = 0;
     
	for(; poz > 0; poz -= ubit(poz))
     rez += A[poz], rez = rez >= MOD ? rez - MOD : rez;
     return rez;
}

void easy()
{
     freopen("distincte.ok", "w", stdout);
     int i, j, a, b, rezz = 0;
     
     for(i = 0; i < M; i++)
     {
     	a = Q[i].y, b = Q[i].x;
          rezz = 0;
          memset(seen, 0, sizeof(seen));
     	for(; a <= b; a++)
          if(!seen[v[a]]) rezz += v[a], rezz = rezz >= MOD ? rezz - MOD : rezz, seen[v[a]] = 1;
          printf("%d\n", rezz);
     }
}