#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,maxim,nr,pos,lg,x,y,k,nr_buckets,maxim2,nr2;
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 = (sum + v[j]) % 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;
        for (j=poz_bucket[i].dr+1;j<=n;j++){
            f[v[j]]++;
            if (f[v[j]] == 1)
                sum = (sum + v[j]) % MOD;

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

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

                /// acum demarchez
                for (int t=qry[buckets[i][pos]].st;t<=poz_bucket[i].dr;t++)
                    f[v[t]]--;

                pos++;
            }}

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

    return 0;
}