#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int v[100001];
struct str {
    int a,b,ind,rez;
};
vector <str> query;
int aib[100001];
int urm[100001];
const int mod = 666013;

int qu(int v) {
    int sum=0;
    for (int i=v;i>=1;i-=i&(-i)) {
        sum=(sum+aib[i])%mod;
    }
    return sum;
}

void update(int poz,int val,int n) {
    for (int i=poz;i<=n;i+=i&(-i)) {
        aib[i]=(aib[i]+val)%mod;
        if (aib[i] < 0) aib[i] += mod;
    }
}

int main() {
    int n,k,m;
    fin >> n >> k >> m;
    for (int i=1;i<=n;i++) {
        fin >> v[i];
    }
    for (int i=1;i<=m;i++) {
        int a,b;
        fin >> a >> b;
        query.push_back({a,b,i});
    }
    sort(query.begin(),query.end(),[](str a,str b) {
        return a.b<b.b;
    });
    int aux=0;
    for (int i=1;i<=n;i++) {
        if (urm[v[i]]==0) {
            update(i,v[i],n);
            urm[v[i]]=i;
        }else {
            update(i,v[i],n);
            update(urm[v[i]],-v[i],n);
            urm[v[i]]=i;
        }
        while (query[aux].b==i) {
            query[aux].rez=qu(query[aux].b)-qu(query[aux].a-1);
            aux++;
        }
    }
    sort(query.begin(),query.end(),[](str a,str b) {
        return a.ind<b.ind;
    });
    for (int i=0;i<query.size();i++) {
        fout << query[i].rez << "\n";
    }
    return 0;
}