#include <cstdio>
#include <algorithm>

using namespace std;

struct qry{
    int x; int y; int c;
};

int n, i, j, k, m, v[100100], x[100100], t[100100];
long long rez[100100], sol[100100];
qry s[100100]; 

bool cmp(qry a, qry b) {
    if (a.y < b.y)
        return true;
    else 
        return false;
}

int lsb(int x) {
    return (x&(x-1))^x;   
}

void update(int a, int b) {
    while (a<=n) {
        x[a] = x[a] + b;
        a+=lsb(a);        
    }    
}

long long query(int a) {
    long long r=0;
    while (a) {
        r = (r + x[a]) % 666013;
        a -= lsb(a);    
    }    
    return r;
}


int main(){
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    
    scanf("%d%d%d", &n, &k, &m);
    
    for (i=1; i<=n; i++)
        scanf("%d", &v[i]);
        
    for (i=1; i<=m; i++) {
        scanf("%d%d", &s[i].x, &s[i].y);
        s[i].c = i;
    }
    
    sort(s+1, s+m+1, cmp);
    
    for (i=1; i<=m; i++) {
        for (j=s[i-1].y+1; j<=s[i].y; j++) {
            if (t[v[j]] != 0)
                update(t[v[j]], -v[j]);
            update(j, v[j]);
            t[v[j]] = j;
        }
        
        rez[i] = query(s[i].y) - query(s[i].x - 1);
    }
    
        
    for (i=1; i<=m; i++)
        sol[s[i].c] = rez[i];
        
    for (i=1; i<=m; i++)
        printf("%lld\n", sol[i]);

    return 0;
}