#include <bits/stdc++.h>

using namespace std;

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

int n,v[Nmax],last[Nmax];
long long aib[Nmax],sol[Nmax];

int lsb(int x) {
    return x&(-x);
}
void update(int poz, int val) {
    for (int i=poz; i<=n; i+=lsb(i)) {
        aib[i]+=val;
    }
}
long long query(int poz) {
    long long s=0;
    for (int i=poz; i>0; i-=lsb(i)) {
        s+=aib[i];
        s%=MOD;
    }
    return s%MOD;
}

struct interval {
    int st,dr,nr;
} q[Nmax];
bool cmp (interval i1, interval i2){
    return i1.dr<i2.dr;
}

int main()
{
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    int m,k;
    fin>>n>>k>>m;
    for (int i=1; i<=n; ++i) {
        fin>>v[i];
    }
    for (int i=1; i<=m; ++i) {
        fin>>q[i].st>>q[i].dr;
        q[i].nr=i;
    }
    sort(q+1,q+m+1,cmp);
    int j=1;
    for (int i=1; i<=n; ++i) {
        update(i,v[i]);
        if (last[v[i]]!=0) update(last[v[i]],-v[i]);
        last[v[i]]=i;
        while (i==q[j].dr) {
            sol[q[j].nr]=(query(q[j].dr)-query(q[j].st-1))%MOD;
            j++;
        }
    }
    for (int i=1; i<=m; ++i) {
        fout<<sol[i]<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}