#include <bits/stdc++.h>
#define DIM 100010
#define MOD 666013
using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
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 (){

    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;
}