#include<stdio.h>
#include<vector>
#include<algorithm>

#define NMAX 100007

using namespace std;

struct Dist{
    int x;
    int y;
    int Ind;
    int Ans;
};

vector<Dist> q;
int n, aib[NMAX], Ap[NMAX], Aux[NMAX], a[NMAX], k, m;

Dist make_Dist(int xx, int yy, int IND){
    Dist b;
    b.x = xx;
    b.y = yy;
    b.Ind = IND;
    return b;
}

int MOD(int a){
    if(a > 666013)
        a -= 666013;
    return a;
}

int cmp1(Dist a, Dist b){
    return a.y < b.y;
}

int  cmp2(Dist a, Dist b){
    return a.Ind < b.Ind;
}

void update(int poz, int val){
    while (poz <= n){
        aib[poz] += val;
        poz += poz & (poz ^ (poz - 1));
    }
}
int query(int poz){
    int sol = 0;
    while (poz){
        sol += aib[poz];
        poz -= poz & (poz ^ (poz - 1));
    }
    return sol;
}

void solve(){
    int Nr = 1, AM = 0;
    while(Nr <= n && AM < q.size()){
        if(Ap[a[Nr]] > 0){
            Aux[Ap[a[Nr]]] = 0;
            update(Ap[a[Nr]], - a[Ap[a[Nr]]]);
            Ap[a[Nr]] = Nr;
            Aux[Nr] = 1;
            update(Nr, a[Nr]);
        }
        else{
            Ap[a[Nr]] = Nr;
            Aux[Nr] = 1;
            update(Nr, a[Nr]);
        }
        while(q[AM].y == Nr){
            q[AM].Ans = query(q[AM].y) - query(q[AM].x - 1);
            q[AM].Ans = MOD(q[AM].Ans);
            ++ AM;
        }
        ++ Nr;
    }
}

int main(){
    freopen("distincte.out", "w", stdout);
    freopen("distincte.in", "r", stdin);
    scanf("%d %d %d", &n, &k, &m);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= m; ++ i){
        int xx, yy;
        scanf("%d %d", &xx, &yy);
        q.push_back(make_Dist(xx, yy, i));
    }
    sort(q.begin(), q.end(), cmp1);
    solve();
    sort(q.begin(), q.end(), cmp2);
    for(int i = 0; i < m; ++ i)
        printf("%d\n", q[i].Ans);
    return 0;
}