#include <iostream>
#include <algorithm>

#define NMAX 100004
#define MOD 666013

using namespace std;

struct interval
{
    int pos;
    int val;
    int next;
};

struct Query
{
    int st;
    int dr;
    int pos;
};

int N, K, M, last[NMAX], T[4*NMAX], v_pos = 1, pos, S, E, val = 0;
int O[NMAX];
interval v[NMAX];
Query Q[NMAX];

void build(int node, int st, int dr)
{
    if(st == dr)
    {
        T[node] = v[st].val;
    }
    else
    {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        T[node] = (T[2 * node] + T[2 * node + 1]) % MOD;
    }
}

void update(int node, int st, int dr)
{
    if(st == dr)
    {
        T[node] = 0;
    }
    else
    {
        int mid = (st + dr) / 2;
        if(pos <= mid)
        {
            update(2 * node, st, mid);
        }
        else
        {
            update(2 * node + 1, mid + 1, dr);
        }
        T[node] = (T[2 * node] + T[2 * node + 1]) % MOD;
    }
}

void query(int node, int st, int dr)
{
    if(S <= st && dr <= E)
    {
        val = (val + T[node]) % MOD;
    }
    else
    {
        int mid = (st + dr) / 2;
        if(S <= mid)
        {
            query(2 * node, st, mid);
        }
        if(E > mid)
        {
            query(2 * node + 1, mid + 1, dr);
        }
    }
}


bool cmp_interval(interval A, interval B) {
    return A.next < B.next;
}

bool cmp_query(Query A, Query B) {
    return A.dr < B.dr;
}

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

    scanf("%d %d %d", &N, &K, &M);

    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &v[i].val);
        v[i].next = N + 1;
        v[i].pos = i;
        v[last[v[i].val]].next = i;
        last[v[i].val] = i;
    }

    build(1, 1, N);

    for(int i = 1; i <= M; i++)
    {
        scanf("%d %d", &Q[i].st, &Q[i].dr);
        Q[i].pos = i;
    }

    sort(v + 1, v + N + 1, cmp_interval);
    sort(Q + 1, Q + M + 1, cmp_query);

    for(int i = 1; i <= M; i++)
    {
        while(v_pos <= N && v[v_pos].next <= Q[i].dr)
        {
            pos = v[v_pos].pos;
            update(1, 1, N);
            v_pos++;
        }
        S = Q[i].st;
        E = Q[i].dr;
        val = 0;
        query(1, 1, N);
        O[Q[i].pos] = val;
    }

    for(int i = 1; i <= M; i++) {
        printf("%d\n", O[i]);
    }

    return 0;
}