#include <iostream>
#include <fstream>
#include <algorithm>

#define ENDL '\n'
#define mod 666013

using namespace std;

struct query{
    int ind;
    int st, dr;

    friend bool operator<(query q1, query q2){
        return q1.dr<q2.dr;
    }
};

query q[100001];

int n;

long long aib[100001], sol[100001];
int v[100001], poz[100001];

long long query_aib(int p){
    long long rez=0;

    for(int i=p; i>0; i-=(i&-i)){
        rez+=aib[i];
    }

    return rez;
}

void update_aib(int p, int x){
    for(int i=p; i<=n; i+=(i&-i)){
        aib[i]+=x;
    }
}

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

    int k, m; fin>>n>>k>>m;

    for(int i=0; i<n; i++){
        fin>>v[i];
    }

    for(int i=0; i<m; i++){
        int st, dr; fin>>st>>dr;

        q[i]=query({i, st-1, dr-1});
    }

    sort(q, q+m);

    int j=0;
    for(int i=0; i<m; i++){
        while(j<q[i].dr){
            j++;

            if(poz[v[j]]) update_aib(poz[v[j]], -v[j]);

            poz[v[j]]=j;
            update_aib(j, v[j]);
        }

        sol[q[i].ind]=(query_aib(q[i].dr)-query_aib(q[i].st-1)+mod)%mod;
    }

    for(int i=0; i<m; i++){
        fout<<sol[i]<<ENDL;
    }

    return 0;
}