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

#define nmax 100005
#define modulo 666013

using namespace std;

int n,k,m;
int a[nmax],ix[nmax],iy[nmax],place[nmax],val[nmax],arb[262144],last[nmax];

int cmp(int i,int j) {
    return iy[j] > iy[i];
}

int query(int nod,int st,int dr,int x) {
    if(x <= st && dr <= x) return arb[nod];
    else {
        int mij = (st + dr) / 2;
        int r = arb[nod];
        if(x <= mij) {
            r += query(nod * 2,st,mij,x) % modulo;
            if(r >= modulo) r -= modulo;
            if(r < 0) r += modulo;
        }
        if(x > mij) {
            r += query(nod * 2 + 1,mij + 1,dr,x) % modulo;
            if(r >= modulo) r -= modulo;
            if(r < 0) r += modulo;
        }
        return r;
    }
}

void update(int nod,int st,int dr,int a,int b,int v) {
    if(st == 0 || dr == 0 || a == 0 || b == 0) return ;
    if(a <= st && dr <= b) {
        arb[nod] += v;
        if(arb[nod] < modulo) arb[nod] += modulo;
        if(arb[nod] >= modulo) arb[nod] -= modulo;
    }
    else {
        int mij = (st + dr) / 2;
        if(a <= mij) update(nod * 2,st,mij,a,b,v);
        if(b > mij) update(nod * 2 + 1,mij + 1,dr,a,b,v);
    }
}

int main() {    
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    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++) {       
        scanf("%d%d",&ix[i],&iy[i]);
        place[i] = i;
    }
   
    sort(place + 1,place + m + 1,cmp);  

    int pz = 0;
    for(int i = 1; i <= m; i++) {
        int pzx = ix[place[i]];
        int pzy = iy[place[i]];
        while(pz < pzy) {
            if(last[a[pz + 1]] != 0) update(1,1,n,1,last[a[pz + 1]],-a[pz + 1]);
            update(1,1,n,1,pz + 1,a[pz + 1]);
            last[a[pz + 1]] = pz + 1;
            pz++;              
        }
        val[place[i]] = query(1,1,n,pzx);
        if(val[place[i]] > modulo) val[place[i]] -= modulo;
    }

    for(int i = 1; i <= m; i++) printf("%d\n",val[i]);

    return 0;
}