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

#define NMAX 131072
#define LOGMAX 18
#define PX 666013
#define MAX_DIM 0

struct ORSTinfo {
	int ORSTdim;
	int *ORSTci, *ORSTcs;
	int *ORSTx, **ORSTy, **ORSTsum;
	int **ORSTpoz, **ORSTnextdif, *ORSTmaxson[2];
	char **ORSTson;
} *orsti[2 * NMAX];

int v[NMAX], poz[NMAX], vaux[NMAX], paux[NMAX], ci[NMAX * 2], cs[NMAX * 2], sum[NMAX * 2];
int vx[NMAX >> 1], vy[NMAX >> 1], ve[NMAX >> 1];
int i, j, k, l, N, M, P;

void msortvx(int li, int ls, int n)
{
	int i, j, k, m;

	if (li >= ls)
		return;

	m = (li + ls) >> 1;

	msortvx(li, m, n);
	msortvx(m + 1, ls, n);

	i = k = li; j = m + 1;

	while (i <= m && j <= ls)
	{
		if (vx[i] < vx[j])
		{
			orsti[n]->ORSTx[k] = vx[i];
			orsti[n]->ORSTy[0][k] = vy[i];
			orsti[n]->ORSTsum[0][k] = ve[i];
			k++;
			i++;
		}
		else
		{
			orsti[n]->ORSTx[k] = vx[j];
			orsti[n]->ORSTy[0][k] = vy[j];
			orsti[n]->ORSTsum[0][k] = ve[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			orsti[n]->ORSTx[k] = vx[j];
			orsti[n]->ORSTy[0][k] = vy[j];
			orsti[n]->ORSTsum[0][k] = ve[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			orsti[n]->ORSTx[k] = vx[i];
			orsti[n]->ORSTy[0][k] = vy[i];
			orsti[n]->ORSTsum[0][k] = ve[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
	{
		vx[k] = orsti[n]->ORSTx[k];
		vy[k] = orsti[n]->ORSTy[0][k];
		ve[k] = orsti[n]->ORSTsum[0][k];
	}
}

void msortORST(int li, int ls, int niv, int n1, int n)
{
	int i, j, k, m;

	if (li > ls)
		return;

	orsti[n]->ORSTci[n1] = li;
	orsti[n]->ORSTcs[n1] = ls;

	if (li >= ls)
	{
		orsti[n]->ORSTy[niv][li] = vy[li];
		orsti[n]->ORSTsum[niv][li] = ve[li] % PX;
		return;
	}

	m = (li + ls) >> 1;

	msortORST(li, m, niv + 1, (n1 << 1), n);
	msortORST(m + 1, ls, niv + 1, (n1 << 1) + 1, n);

	i = li; j = m + 1; k = li;

	while (i <= m && j <= ls)
	{
		if (vy[i] < vy[j])
		{
			orsti[n]->ORSTy[0][k] = vy[i];
			orsti[n]->ORSTsum[0][k] = ve[i];
			k++;
			i++;
		}
		else
		{
			orsti[n]->ORSTy[0][k] = vy[j];
			orsti[n]->ORSTsum[0][k] = ve[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			orsti[n]->ORSTy[0][k] = vy[j];
			orsti[n]->ORSTsum[0][k] = ve[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			orsti[n]->ORSTy[0][k] = vy[i];
			orsti[n]->ORSTsum[0][k] = ve[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
	{
		vy[k] = orsti[n]->ORSTy[0][k];
		ve[k] = orsti[n]->ORSTsum[0][k];
	}

	orsti[n]->ORSTy[niv][li] = vy[li];
	orsti[n]->ORSTsum[niv][li] = ve[li] % PX;

	for (k = li + 1; k <= ls; k++)
	{
		orsti[n]->ORSTy[niv][k] = vy[k];
		orsti[n]->ORSTsum[niv][k] = (orsti[n]->ORSTsum[niv][k - 1] + ve[k]) % PX;
	}
}

void buildORST(int n, int dim)
{
	orsti[n] = (struct ORSTinfo*) malloc(sizeof(struct ORSTinfo));
	orsti[n]->ORSTdim = dim;

	P = 1, l = 1;
	while (P < orsti[n]->ORSTdim)
		P <<= 1, l++;

	/*
	for (i = ORSTdim[n] + 1; i <= P; i++)
		vx[i] = N + i, vy[i] = ve[i] = 0;
	
	ORSTdim[n] = P;
	*/

	orsti[n]->ORSTx = (int *) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
	orsti[n]->ORSTy = (int**) malloc(l * sizeof(int*));
	orsti[n]->ORSTsum = (int**) malloc(l * sizeof(int*));

	for (i = 0; i < 1; i++)
	{
		orsti[n]->ORSTy[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
		orsti[n]->ORSTsum[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
	}

	msortvx(1, orsti[n]->ORSTdim, n);
	
	for (i = 1; i <= orsti[n]->ORSTdim; i++)
		orsti[n]->ORSTx[i] = vx[i];

	for (i = 1; i <= orsti[n]->ORSTdim; i++)
		orsti[n]->ORSTy[0][i] = vy[i],
		orsti[n]->ORSTsum[0][i] = ve[i];

	if (orsti[n]->ORSTdim >= MAX_DIM)
	{
		for (i = 1; i < l; i++)
		{
			orsti[n]->ORSTy[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
			orsti[n]->ORSTsum[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
		}

		orsti[n]->ORSTci = (int *) malloc(2 * (P + 1) * sizeof(int));
		orsti[n]->ORSTcs = (int *) malloc(2 * (P + 1) * sizeof(int));

		msortORST(1, orsti[n]->ORSTdim, 0, 1, n);
	}
	else
		orsti[n]->ORSTci = NULL;
}

inline int q2ORST(int li, int ls, int ymax, int n, int n1, int niv)
{
	int cmid = (orsti[n]->ORSTci[n1] + orsti[n]->ORSTcs[n1]) >> 1;
	int yp, yli, yls, ymid;

	if (li == orsti[n]->ORSTci[n1] && ls == orsti[n]->ORSTcs[n1])
	{
		if (ymax < orsti[n]->ORSTy[niv][orsti[n]->ORSTci[n1]])
			return 0;

		yli = orsti[n]->ORSTci[n1]; yls = orsti[n]->ORSTcs[n1];
		yp = 1;

		while (yli <= yls)
		{
			ymid = (yli + yls) >> 1;

			if (orsti[n]->ORSTy[niv][ymid] <= ymax)
			{
				yp = ymid;
				yli = ymid + 1;
			}
			else
				yls = ymid - 1;
		}

		return orsti[n]->ORSTsum[niv][yp];
	}

	if (ls <= cmid)
		return q2ORST(li, ls, ymax, n, (n1 << 1), niv + 1);

	if (li > cmid)
		return q2ORST(li, ls, ymax, n, (n1 << 1) + 1, niv + 1);

	return (q2ORST(li, cmid, ymax, n, (n1 << 1), niv + 1) + q2ORST(cmid + 1, ls, ymax, n, (n1 << 1) + 1, niv + 1)) % PX;
}

inline int qORST(int xmax, int ymax, int n)
{
	int xp, li, ls, mid, rez;

	if (orsti[n] == NULL)
		return 0;

	if (orsti[n]->ORSTci == NULL)
	{
		rez = 0;

		for (li = 1; li <= orsti[n]->ORSTdim && orsti[n]->ORSTx[li] <= xmax; li++)
			if (orsti[n]->ORSTy[0][li] <= ymax)
				rez = (rez + orsti[n]->ORSTsum[0][li]) % PX;

		return rez;
	}

	li = 1; ls = orsti[n]->ORSTdim;
	xp = 0;

	while (li <= ls)
	{
		mid = (li + ls) >> 1;

		if (orsti[n]->ORSTx[mid] <= xmax)
		{
			xp = mid;
			li = mid + 1;
		}
		else
			ls = mid - 1;
	}

	if (xp > 0)
		return q2ORST(1, xp, ymax, n, 1, 0);
	
	return 0;
}

void mergesort(int li, int ls, int n)
{
	int m, dim;

	if (li > ls || n > (2 * NMAX - 1))
		return;

	ci[n] = li;
	cs[n] = ls;
	dim = 0;
	orsti[n] = NULL;

	if (li >= ls)
	{
		sum[n] = v[li] % PX; 
		return;
	}

	m = (li + ls) >> 1;

	mergesort(li, m, n << 1);
	mergesort(m + 1, ls, (n << 1) + 1);

	// compute position intervals

	i = li; j = m + 1;

	while (i <= m && j <= ls)
	{
		while (i < m && v[i] == v[i + 1])
			i++;

		if (v[i] == v[j])
		{
			// we have common position interval [ poz[i], poz[j] ]

			//fprintf(stderr, "n=%d,v=%d,p1=%d,x=%d,cmid=%d,p2=%d\n", n, v[i], poz[i], m - poz[i] + 1, m, poz[j]);

			dim++;
			vx[dim] = m - poz[i] + 1;
			vy[dim] = poz[j];
			ve[dim] = v[i];
			//ve.push_back(make_pair(v[i], make_pair(cmid[n] - poz[i] + 1, poz[j])));

			while (j < ls && v[j] == v[j + 1])
				j++;
			j++;
		}
		else
		if (v[i] < v[j])
			i++;
		else
		{
			while (j < ls && v[j] == v[j + 1])
				j++;
			j++;
		}
	}

	// build an orthogonal range search tree for the common pairs

	if (dim > 0)
		buildORST(n, dim);

	// merge

	i = li; j = m + 1; k = li;

	while (i <= m && j <= ls)
	{
		if (v[i] <= v[j])
		{
			vaux[k] = v[i];
			paux[k] = poz[i];
			k++;
			i++;
		}
		else
		{
			vaux[k] = v[j];
			paux[k] = poz[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			vaux[k] = v[j];
			paux[k] = poz[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			vaux[k] = v[i];
			paux[k] = poz[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
		v[k] = vaux[k],
		poz[k] = paux[k];

	sum[n] = v[li] % PX;
	for (k = li + 1; k <= ls; k++)
		if (v[k] > v[k - 1])
			sum[n] = (sum[n] + v[k]) % PX;
}

inline int query(int li, int ls, int n)
{
	int cmid = (ci[n] + cs[n]) >> 1;

	if (li == ci[n] && ls == cs[n])
		return sum[n];

	if (ls <= cmid)
		return query(li, ls, (n << 1));

	if (li > cmid)
		return query(li, ls, (n << 1) + 1);

	return (query(li, cmid, (n << 1)) + query(cmid + 1, ls, (n << 1) + 1) - qORST(cmid - li + 1, ls, n) + PX) % PX;
}

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

	scanf("%d %d %d", &N, &k, &M);

	for (i = 1; i <= N; i++)
		scanf("%d", &v[i]);

	/*	
	P = 1;
	while (P < N)
		P <<= 1;

	for (i = N + 1; i <= P; i++)
		v[i] = 0;
	
	N = P;
	*/

	//fprintf(stderr, "%d\n", P);

	for (i = 1; i <= N; i++)
		poz[i] = i;

	mergesort(1, N, 1);

	freopen("distincte.out", "w",stdout);

	while (M--)
	{
		scanf("%d %d", &i, &j);
		printf("%d\n", query(i, j, 1));
	}

	return 0;
}