#include<cstdio>
#include<algorithm>
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "distincte.in"
#define outfile "distincte.out"
#define zeros(x) (x & -x)
#define MOD 666013LL
#define nMax 100005
using namespace std;

struct query{
    int left, right;
    int ans, idx;

    bool operator < (const query &that)const{
        return right < that.right;
    }
} Q[nMax];

int AIB[nMax];

int V[nMax], Last[nMax];

int N, M, K;

bool cmp(const query &a, const query &b){
    return a.idx < b.idx;
}

void read(){
    freopen(infile, "r", stdin);

    scanf("%d %d %d", &N, &K, &M);

    FOR(i,1,N)
       scanf("%d", &V[i]);

    FOR(i,0,M-1){
        scanf("%d %d", &Q[i].left, &Q[i].right);
        Q[i].idx = i;
    }

    fclose(stdin);
}

void update(int x, int val){
    for(; x <= N; x += zeros(x))
       AIB[x] = (0LL + AIB[x] + val) % MOD;
}

int query(int x){
    int res = 0;
    for(; x > 0; x -= zeros(x))
       res = (0LL + res + AIB[x]) % MOD;
    return res;
}

void solve(){
    sort(Q, Q+M);

    int iQ = 0;
    FOR(i,1,N){
        if(Last[V[i]])
           update(Last[V[i]], -V[i]);

        Last[V[i]] = i;
        update(i, V[i]);

        while(Q[iQ].right == i && iQ < M){
            Q[iQ].ans = (0LL + query(Q[iQ].right) - query(Q[iQ].left - 1) + 2 * MOD) % MOD;
            iQ ++;
        }
    }

    sort(Q, Q+M, cmp);
}

void print(){
    freopen(outfile, "w", stdout);

    FOR(i,0,M-1)
        printf("%d\n", Q[i].ans);

    fclose(stdout);
}

int main(){
    read();
    solve();
    print();

    return 0;
}