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

using namespace std;

#define MAX_N 100010
#define prim 666013

int a[MAX_N],aib[MAX_N],poz[MAX_N],apar[MAX_N],fin[MAX_N];
int i,j,k,n,m,suma;

struct inter{
       int x;
       int y;
};

inter v[MAX_N];

inline int cmp(int p, int q) {
       return v[p].y < v[q].y;
}

void cit() {
    scanf("%d %d %d",&n,&k,&m);
    for (i = 1; i <= n; poz[i] = i, i++) 
        scanf("%d ",&a[i]);
    
    for (i = 1; i <= m; i++) 
        scanf("%d %d",&v[i].x,&v[i].y);
    
}

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

void update(int p) {
     int k = p;
     while (k <= n) {
           aib[k] += a[p];
           k += lsb(k);
     }
}

void scoate(int p) {
     if (!p) return;

     int k = p;
     while (k <= n) {
           aib[k] -= a[p];
           k += lsb(k);
     }
}

int sum(int p) {
     int k = p, suma = 0;
     while (k > 0) {
           suma += aib[k];
           k -= lsb(k);
     }
     
     return suma;
}

void solve() {
     sort(poz + 1, poz + m + 1, cmp);
     v[m + 1] = v[m];
     
     for (i = 1; i <= m; i++) {
         for (j = v[poz[i - 1]].y + 1; j <= v[poz[i]].y; j++) {
             scoate(apar[a[j]]);
             update(j);
             apar[a[j]] = j;
         }

         fin[poz[i]] = sum(v[poz[i]].y) - sum(v[poz[i]].x - 1);
     }
}

void write() {
    for (i = 1; i <= m; i++)
        printf("%d\n",fin[i] % prim);
}

int main() {

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

    cit();
    solve();
    write();

    return 0;
}