#include <iostream>
#include <algorithm>

#define NMAX 100004
#define MOD 666013

using namespace std;



class InParser {
  private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

  public:
    InParser(const char *nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser &operator>>(int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-')
            ;
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser &operator>>(long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-')
            ;
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

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];
        if(T[node] >= MOD) {
            T[node] -= 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];
        if(T[node] >= MOD) {
            T[node] -= MOD;
        }
    }
}

void query(int node, int st, int dr)
{
    if(S <= st && dr <= E)
    {
        val = val + T[node];
        if(val > MOD ){
            val -= 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()
{
    InParser fin("distincte.in");
    FILE *out = fopen("distincte.out", "w");

    fin >> N >> K >> M;

    for(int i = 1; i <= N; i++)
    {
        fin >> 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++)
    {
        fin >> 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++) {
        fprintf(out, "%d\n", O[i]);
    }

    return 0;
}