#include <bits/stdc++.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser fin("distincte.in");
ofstream fout("distincte.out");

const int MOD = 666013, NMAX = 1e5 + 5;
long long AIB[NMAX], n, k, q;
int w[NMAX];
int last[NMAX];

inline void update_aib(int pos, int val)
{
    while(pos <= n)
    {
        AIB[pos] += val;
        pos += pos & -pos;
    }
}

inline long long query_aib(int pos)
{
    long long sol = 0;
    while(pos > 0)
    {
        sol += AIB[pos];
        pos -= pos & -pos;
    }

    return sol;
}

///retin in intervale unde se afla fiecare element si fac query urile in ordine inversa
int nrinterv;
struct hlp
{
    int st, dr, val;
}interv[NMAX];

inline bool cmp(hlp a, hlp b)
{
    return a.dr > b.dr;
}

struct queryyy
{
    int st, dr, index;
    long long sol = 0;
}qq[NMAX];

inline bool cmp2(queryyy a, queryyy b)
{
    return a.dr > b.dr;
}

inline bool cmp3(queryyy a, queryyy b)
{
    return a.index < b.index;
}

inline void citire()
{
    memset(AIB, 0, sizeof(AIB));
    memset(w, 0, sizeof(w));
    memset(last, 0, sizeof(last));
    fin >> n >> k >> q;
    int i;
    for(i = 1; i <= n; ++i)
        fin >> w[i];

    for(i = 1; i <= k; ++i)
        last[i] = n + 1;

    for(i = n; i > 0; --i)
    {
        interv[++nrinterv].st = i;
        interv[nrinterv].dr = last[w[i]];
        last[w[i]] = i;
        interv[nrinterv].val = w[i];
    }


    for(i = 1; i <= q; ++i)
        fin >> qq[i].st >> qq[i].dr, qq[i].index = i;

    sort(interv + 1, interv + 1 + nrinterv, cmp);
    sort(qq + 1, qq + 1 + q, cmp2);

    int intervalCurent = 1;
    for(i = 1; i <= q; ++i)
    {
        while(intervalCurent <= nrinterv && interv[intervalCurent].dr > qq[i].dr)
            update_aib(interv[intervalCurent].st, interv[intervalCurent].val), ++intervalCurent;
        qq[i].sol = query_aib(qq[i].dr) - query_aib(qq[i].st - 1);
        qq[i].sol %= MOD;
    }

    sort(qq + 1, qq + 1 + q, cmp3);

    for(i = 1; i <= q; ++i)
        fout << qq[i].sol << '\n';

}

int main()
{
    citire();


    return 0;
}