#include<fstream>
#include<cstring>
#include<algorithm>

using namespace std;

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

#define NMAX 100006
#define zero(x) ((x ^ (x - 1) ) & x)
#define MOD 666013

int AIB[NMAX]; int M; int K; int N; int next[NMAX]; int ant[NMAX]; int v[NMAX];

struct interval{
int st; int dr; int s; int ind;
};

interval I[NMAX];

void add(int x, int val){
    for(int i = x; i <= N; i += zero(i)){
        AIB[i] += val;
        if(AIB[i] >= MOD)
            AIB[i] -= MOD;
        if(AIB[i] < 0 )
            AIB[i] += MOD;
    }
}

long long comp(int max_bound){
    long long S = 0;
    for(int i = max_bound; i ; i -= zero(i))
            S += AIB[i];
    return S % MOD;
}

void Read (){
    fin >> N>> K>> M;

    for(int i = 1; i <= N; i++){
        int a;
        fin >>a;
        v[i] = a;
        next[ant[a]] = i;
        if(!ant[a])
            add(i, a);
        ant[a] = i;
    }

}

bool cmp(interval A, interval B){
    return A.st < B.st;
}


bool cmp2(interval A, interval B){
    return A.ind < B.ind;
}
void Solve (){
    for(int i = 1 ;i <= M; ++i){
        fin >> I[i].st >> I[i].dr;
        I[i].ind = i;
    }

    sort(&I[1], &I[M + 1], cmp);
    int cnt = 1;
    for(int i = 1; i <= N; ++i){
        while(cnt <= M && I[cnt].st == i){
            I[cnt].s = comp(I[cnt].dr);
            cnt++;
        }
        add(i, -v[i]);
        if(next[i]) add(next[i], v[i]);
    }
    sort(&I[1] , &I[1 + M], cmp2);
    for(int i = 1; i <= M; i++)
        fout << I[i].s <<'\n';

}
int main(){

    Read ();

    Solve ();

    return 0;
}