#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]);
    }
}