#include <cstdio>

const int MAX_SIZE(100001);
const int MOD(666013);

int numbers [MAX_SIZE];
int next_index [MAX_SIZE];
int bit [MAX_SIZE];
int solution [MAX_SIZE];

int heap_size;

struct query
{
	int index;
	int left;
	int right;
} heap [MAX_SIZE];

inline bool operator > (struct query a, struct query b)
{
	if (a.left > b.left)
		return true;
	return false;
}

inline void operator ^= (struct query &a, struct query &b)
{
	a.index ^= b.index;
	a.left ^= b.left;
	a.right ^= b.right;
}

inline void swap (int a, int b)
{
	heap[a] ^= heap[b];
	heap[b] ^= heap[a];
	heap[a] ^= heap[b];
}

inline void heap_up (void)
{
	if (heap_size == 1)
		return;
	int index(heap_size), father(index >> 1);
	struct query value(heap[index]);
	while (true)
	{
		if (value > heap[father])
			heap[index] = heap[father];
		else
			break;
		index = father;
		if (father > 1)
			father >>= 1;
		else
			break;
	}
	heap[index] = value;
}

inline void heap_down (void)
{
	int index(1), left(2), right(3), greatest;
	while (true)
	{
		if (left <= heap_size && heap[left] > heap[index])
			greatest = left;
		else
			greatest = index;
		if (right <= heap_size && heap[right] > heap[greatest])
			greatest = right;
		if (greatest == index)
			break;
		swap(index,greatest);
		index = greatest;
		left = index << 1;
		right = left + 1;
	}
}

inline void push (int index, int left, int right)
{
	++heap_size;
	heap[heap_size].index = index;
	heap[heap_size].left = left;
	heap[heap_size].right = right;
	heap_up();
}

inline void pop (void)
{
	heap[1] = heap[heap_size];
	--heap_size;
	heap_down();
}

inline int lsb (int x)
{
	return x & -x;
}

inline void bit_unique_update (const int value, int index, const int size)
{
	const int position(index);
	while (index <= size)
	{
		bit[index] += value;
		if (bit[index] >= MOD)
			bit[index] -= MOD;
		index += lsb(index);
	}
	index = next_index[value];
	if (index)
		while (index <= size)
		{
			bit[index] -= value;
			if (bit[index] < 0)
				bit[index] += MOD;
			index += lsb(index);
		}
	next_index[value] = position;
}

inline int bit_query (int index)
{
	int sum(0);
	while (index)
	{
		sum += bit[index];
		if (sum >= MOD)
			sum -= MOD;
		index -= lsb(index);
	}
	return sum;
}

int main (void)
{
	std::freopen("distincte.in","r",stdin);
	std::freopen("distincte.out","w",stdout);
	int n, k, m;
	std::scanf("%d%d%d",&n,&k,&m);
	int *iterator, *end;
	for (iterator = numbers + 1, end = numbers + n ; iterator <= end ; ++iterator)
		std::scanf("%d",iterator);
	int index, left, right, *left_ptr(&left), *right_ptr(&right);
	for (index = 0 ; index < m ; ++index)
	{
		std::scanf("%d%d",left_ptr,right_ptr);
		push(index,left,right);
	}
	std::fclose(stdin);
	index = n;
	while (heap_size)
	{
		left = heap[1].left;
		right = heap[1].right;
		while (index && index >= left)
		{
			bit_unique_update(numbers[index],index,n);
			--index;
		}
		solution[heap[1].index] = bit_query(right);
		pop();
	}
	for (iterator = solution, end = solution + m ; iterator < end ; ++iterator)
		std::printf("%d\n",*iterator);
	std::fclose(stdout);
	return 0;
}