#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

struct que {
    int a,b,p;
    que(int _a=0,int _b=0, int _p=0) {
        a=_a;
        b=_b;
        p=_p;
    }
};

inline bool operator < (const que &a,const que &b) {
    return a.b<b.b;
}

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

const int MAX_N=100100;


int N;

int ans[MAX_N];
int v[MAX_N];
vector<que> Q;

int lap[MAX_N];
long long aib[MAX_N];

void update(int poz,int val) {
    while(poz<=N) {
        aib[poz]+=val;
        poz+=(poz&(-poz));
    }
}

long long query(int poz) {
    long long sum=0;
    while(poz) {
        sum+=aib[poz];
        poz-=(poz&(-poz));
    }
    return sum;
}

inline int query(int a,int b) {
    return (query(b)-query(a-1))%666013;
}

int main() {
    int 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;
        Q.push_back(que(a,b,i));
    }
    sort(Q.begin(),Q.end());

    vector<que>::iterator it=Q.begin();

    for(int i=1;i<=N;i++) {
        if(it==Q.end()) {
            break;
        }
        
        if(lap[v[i]]) {
            update(lap[v[i]],-v[i]);
        }
        
        lap[v[i]]=i;
        update(i,v[i]);
        
        while(it!=Q.end() && it->b == i) {
            ans[it->p]=query(it->a,it->b);
            it++;
        }
    }
    
    for(int i=1;i<=M;i++) {
        fout<<ans[i]<<'\n';
    }

    return 0;
}