#include <stdio.h>

#define MAX_N 100010

int n,i,j,k,m;
int a[MAX_N],ap[MAX_N];

struct inter{
       int x;
       int y;
};

inter v[MAX_N];

void cit() {

    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 ",&a[i]);
    
    for (i = 1; i <= m; i++) 
        scanf("%d %d",&v[i].x,&v[i].y);
    
}

void solve() {
     
     for (i = 1; i <= m; i++) {
         for (j = 0; j <= k; j++) ap[j] = 0;
         for (j = v[i].x; j <= v[i].y; j++) 
             ap[a[j]] = 1;
         long long suma = 0;
         for (j = v[i].x; j <= v[i].y; j++) 
             ap[a[j]] = 1;
         for (j = 0; j <= k; j++)
             if (ap[j]) suma += j;
         
         printf("%lld\n",suma % 666013);
     }
}

int main() {
    
    cit();
    solve();
    
    return 0;
}