#include <fstream>
#include <algorithm>
using namespace std;

const int MOD = 666013;

template <class TData, class TOver>
class FenwickTree{
public:
    TData* data;
    int len;

    TOver Query(int i)
    {
        TOver sum = 0;
        while(i > 0)
        {
            sum = (sum + data[i]) % MOD;
            i -= (i & (-i));
        }
        return sum;
    }

    void Update(int i, TData delta)
    {
        ++i;
        while(i < len)
        {
            data[i] += delta;
            i += (i & (-i));
        }
    }

    FenwickTree(int capacity)
    {
        len = capacity + 1;
        data = (TData*) calloc(len, sizeof(TData));
    }
};

struct Query
{
	int lft, rght, index;
};

bool cmp(Query a, Query b)
{
	if(a.rght == b.rght)
		return a.lft < b.lft;
	return a.rght < b.rght;
}

int main()
{
	ifstream cin ("distincte.in");
	ofstream cout("distincte.out");

    int n, m, k;
    cin >> n >> k >> m;

    FenwickTree<int,int> aib = *(new FenwickTree<int,int>(n));
    int* arr = (int*) malloc(n * sizeof(int));
    int* ans = (int*) malloc(n * sizeof(int));
    int* lastSeenAt = (int*) calloc(k, sizeof(int));
    Query* queries = (Query*) malloc(m * sizeof(Query));


    for(int i = 0; i < n; i++)
		cin >> arr[i];
    for(int i = 0; i < m; i++)
	{
		cin >> queries[i].lft >> queries[i].rght;
		queries[i].index = i;
	}


	sort(queries, queries + m, cmp);
	int prev = 1;
	for(int i = 0; i < m; i++)
	{
		for(int j = prev; j < queries[i].rght; j++)
		{
			if(lastSeenAt[arr[j]] != 0)
				aib.Update(lastSeenAt[arr[j]], - arr[j]);
			aib.Update(j, arr[j]);
			lastSeenAt[arr[j]] = j;
		}

		int temp = aib.Query(queries[i].rght) - aib.Query(queries[i].lft - 1);
		if(temp < 1)
			temp += MOD;
		ans[queries[i].index] = temp;
		prev = queries[i].rght;
	}


	for(int i = 0; i < m; i++)
		cout << ans[i] << "\n";
    return 0;
}