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

const int MOD = 666013, NMAX = 1e5+5;

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

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

    void Update(int i, TData delta)
    {
        while(i < len)
        {
            data[i] += (delta + MOD);
            data[i] %= MOD;
            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 arr[NMAX];
int ans[NMAX];
int lastSeenAt[NMAX]; /// KMAX
Query queries[NMAX]; /// MMAX


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>(NMAX));
    for(int i = 1; i <= n; i++)
		cin >> arr[i];
    for(int i = 1; i <= m; i++)
	{
		cin >> queries[i].lft >> queries[i].rght;
		queries[i].index = i;
	}


	sort(queries + 1, queries + m + 1, cmp);
	int prev = 1;
	for(int i = 1; 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;
		}

		ans[queries[i].index] = aib.Query(queries[i].rght) - aib.Query(queries[i].lft - 1);
		prev = queries[i].rght;
	}


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