#include <cstdio>
#include <ctype.h>
#include <algorithm>
#define MAXN 100000
#define BUF_SIZE (1<<17)
#define MOD 666013
 
char buf[BUF_SIZE], buf2[BUF_SIZE];
int pos2, poz, sol, n, m, l1, l2, r, pos = BUF_SIZE, oaie, v[MAXN+1], aint[4 * MAXN + 1]; //2 MB
int lista[MAXN+1], next[MAXN+1], val[MAXN+1], last[MAXN+1];
 
FILE *fin, *fout;
 
struct aa{ // 2 MB
    int l1, l2, ans, ind;
}q[MAXN+1];
 
inline char getChar();
inline int getInt();
inline void scrie(int);
inline void putch(char);
 
bool cmp(const aa &v1, const aa &v2){
    return (v1.l1 < v2.l1);
}
 
bool cmp2(const aa &v1, const aa &v2){
    return (v1.ind < v2.ind);
}
 
inline void adauga(int x, int y)
{
    val[++r] = y;
    if(!lista[x]){
        lista[x] = r;
        last[x] = r;
    }
 
    else
    {
        next[last[x]] = r;
        last[x] = r;
    }
}
 
inline void sterge(int x){
    lista[x] = next[lista[x]];
}
 
void update(int st, int dr, int nod)
{
    if(st == dr){
        aint[nod] = oaie;
        return;
    }
    int m = (st+dr)/2;
    if(poz <= m) update(st, m, nod*2);
    if(poz > m) update(m+1, dr, nod*2+1);
 
    aint[nod] = (aint[nod*2] + aint[nod*2+1]) % MOD;
}
 
void query(int st, int dr, int nod)
{
    if(l1 <= st && dr <= l2){
        sol = (sol + aint[nod]) % MOD;
        return;
    }
    int m = (st+dr)/2;
    if(l1 <= m) query(st, m, nod*2);
    if(l2 > m) query(m+1, dr, nod*2+1);
}
 
void dfs(int st, int dr, int nod)
{
    if(st == dr)
    {
        aint[nod] = v[st];
        return;
    }
    int m = (st+dr)/2;
    dfs(st, m, nod*2);
    dfs(m+1, dr, nod*2+1);
 
    aint[nod] = (aint[nod*2] + aint[nod*2+1]) % MOD;
}
 
int main()
{
    fin = fopen("distincte.in", "r");
    fout = fopen("distincte.out", "w");
 
    int i, x, j, k;
 
    n = getInt();
    k = getInt();
    m = getInt();
 
    for(i=1; i<=n; ++i)
    {
        x = getInt();
        if(!lista[x]){
            poz = i;
            oaie = v[i] = x;
        }
        adauga(x, i);
    }
 
    dfs(1, n, 1);
 
    for(i=1; i<=m; ++i){
        q[i].l1 = getInt();
        q[i].l2 = getInt();
        q[i].ind = i;
    }
 
    std::sort(q+1, q+m+1, cmp);
 
    j=1;
    for(i=1; i<=m; ++i)
    {
        while(j<=n && j < q[i].l1){
            if(v[j])
            {
                sterge(v[j]);
                oaie = 0;
                poz = j;
                update(1, n, 1);
 
                oaie = v[j];
                poz = val[lista[v[j]]];
                if(poz){
                    update(1, n, 1);
                    v[poz] = v[j];
                }
            }
            j++;
        }
        l1 = q[i].l1;
        l2 = q[i].l2;
        sol = 0;
        query(1, n, 1);
 
        q[i].ans = sol;
    }
 
    std::sort(q+1, q+m+1, cmp2);
 
    for(i=1; i<=m; ++i){
        scrie(q[i].ans);
        putch('\n');
    }
 
    if(pos2) fwrite(buf2, 1, pos2, fout);
    return 0;
}
 
inline char getChar()
{
    if(pos == BUF_SIZE) pos = 0, fread(buf, 1, BUF_SIZE, fin);
    return buf[pos++];
}
 
inline int getInt()
{
    int nr = 0;
    char c;
 
    c = getChar();
    while(!isdigit(c)) c = getChar();
    while(isdigit(c))
    {
        nr = nr*10 + c-'0';
        c = getChar();
    }
 
    return nr;
}
 
inline void putch(char c)
{
    buf2[pos2++] = c;
    if(pos2 == BUF_SIZE) pos2 = 0, fwrite(buf2, 1, BUF_SIZE, fout);
}
 
inline void scrie(int nr)
{
    char s[10];
    int k=0;
 
    do{
        s[k++] = nr%10 + '0';
        nr /= 10;
    }while(nr);
 
    while(k)
    {
        k--;
        putch(s[k]);
    }
}