#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
#define NMAX 100010
#define MOD 666013
#define ff first
#define ss second
#define RED(x) if (x >= MOD) x -= MOD; if (x < 0) x += MOD;
 
int N, M, K;
 
int a[NMAX];
 
int poz[NMAX];
 
int jeg[NMAX];
 
int nap[NMAX];
 
int aib[NMAX];
 
int naptot[NMAX];
 
pair <pair<int, int>, int> inter[NMAX];
 
inline int lsb(int x) { return (x & (x-1) ^ x); }
 
char ap[NMAX];
 
int rez[NMAX];
 
int query(int x)
{
    int rez = 0;
 
    while (x) {
        rez += aib[x]; RED(rez);
        x -= lsb(x);
    }
 
return rez;
}
 
void update(int x, int sum)
{
//  printf("update - %d %d\n", x, sum);
    while (x <= N) {
        aib[x] += sum; RED(aib[x]);
        x += lsb(x);
    }
}
 
int main()
{
    int i;
     
    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]);
 
        if (!ap[ a[i] ]) update(i, a[i]);
        ap[a[i]] = 1;
 
        nap[ a[i] ] ++;
    }
     
 
    memcpy(naptot, nap, sizeof(nap));
 
    for (i = 1; i <= N; i++) jeg[i] = nap[i] + jeg[i-1];
 
    memset(nap, 0, sizeof(nap));
 
    for (i = 1; i <= N; i++) {
        nap[ a[i] ] ++;
        poz[ jeg[a[i] - 1] + nap[a[i]] ] = i;
    }
 
    for (i = 1; i <= N; i++) nap[i] = 1;
 
    for (i = 1; i <= M; i++) {
        scanf("%d %d", &inter[i].ff.ff, &inter[i].ff.ss);
        inter[i].ss = i;
    }
 
    sort(inter + 1, inter + M + 1);
 
    int ant = 1, j;
 
    for (i = 1; i <= M; i++) {
        for (j = ant; j < inter[i].ff.ff; j++) {
            update(j, -a[j]);
            nap[a[j]]++;
            if (nap[ a[j] ] <= naptot[ a[j] ]) update(poz[ jeg[a[j]-1] + nap[a[j]] ], a[j]);
        }
 
//      printf("%d\n", query( inter[i].ff.ss ));
 
        rez[ inter[i].ss ] = query( inter[i].ff.ss ) - query( inter[i].ff.ff - 1 );
//      printf("%d %d - %d\n", inter[i].ff.ff, inter[i].ff.ss, rez[ inter[i].ss ]);
        RED( rez[ inter[i].ss ] );
        ant = inter[i].ff.ff;
    }
 
    for (i = 1; i <= M; i++) printf("%d\n", rez[i]);
 
fclose(stdin);
fclose(stdout);
return 0;
}