#include <bits/stdc++.h>
#define DIM 100010
#define MOD 666013
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;
	}
};

struct query{
    int st,dr,poz;
};
query qry[DIM],poz_bucket[DIM];
int what_bucket[DIM],v[DIM],f[DIM],sol[DIM];
vector <int> buckets[DIM];
int n,q,i,j,t,pos,lg,x,y,k,nr_buckets;
inline bool cmp (query a, query b){
    if (what_bucket[a.st] == what_bucket[b.st])
        return a.dr < b.dr;
    return what_bucket[a.st] < what_bucket[b.st];
}
int main (){
    InParser fin ("distincte.in");
    ofstream fout ("distincte.out");

    fin>>n>>k>>q;
    for (i=1;i<=n;++i)
        fin>>v[i];

    lg = (int)(n/sqrt(q));
    k = 0;

    for (i=1;i<=q;++i){
        fin>>x>>y;
        if (y-x+1 <= lg){
            int sum = 0;
            for (j=x;j<=y;++j){
                ++f[v[j]];
                if (f[v[j]] == 1){
                    sum += v[j];
                    if (sum >= MOD)
                        sum -= MOD;
                }
            }

            sol[i] = sum;

            for (j=x;j<=y;++j)
                f[v[j]] = 0;

        } else qry[++k] = {x,y,i};
    }
    for (i=1;i<=n;++i){
        if (i % lg)
            what_bucket[i] = i/lg+1;
        else what_bucket[i] = i/lg;

        /*if (poz_bucket[what_bucket[i]].st == 0)
            poz_bucket[what_bucket[i]].st = i;
        poz_bucket[what_bucket[i]].dr = max (poz_bucket[what_bucket[i]].dr,i);*/
    }
    nr_buckets = what_bucket[n];

    sort (qry+1,qry+k+1,cmp);
    for (i=1;i<=k;++i)
        buckets[what_bucket[qry[i].st]].push_back(i);


    for (i=1;i<=nr_buckets;++i){
        int sum = 0, pos = 0;
        int st = (i-1)*lg + 1, dr = min (i*lg,n);
        for (j=dr+1;j<=n;++j){
            ++f[v[j]];
            if (f[v[j]] == 1){
                sum += v[j];
                if (sum >= MOD)
                    sum -= MOD;
            }

            while (pos < buckets[i].size() && j == qry[buckets[i][pos]].dr){

                int sum_aux = sum, idx = buckets[i][pos];
                for (t=qry[idx].st;t<=dr;++t){
                    ++f[v[t]];
                    if (f[v[t]] == 1){
                        sum_aux += v[t];
                        if (sum_aux >= MOD)
                            sum_aux -= MOD;
                    }
                }
                sol[qry[idx].poz] = sum_aux;

                /// acum demarchez
                for (t=qry[idx].st;t<=dr;++t)
                    --f[v[t]];

                ++pos;
            }}

        for (j=dr+1;j<=n;++j)
            f[v[j]] = 0;
    }
    for (i=1;i<=q;++i)
        fout<<sol[i]<<"\n";

    return 0;
}