#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int MOD = 666013, NMAX = 1e5 + 5;
long long AIB[NMAX], n, k, q;
int w[NMAX];
int last[NMAX];

inline void update_aib(int pos, int val)
{
    while(pos <= n)
    {
        AIB[pos] += val;
        pos += pos & -pos;
    }
}

inline long long query_aib(int pos)
{
    long long sol = 0;
    while(pos > 0)
    {
        sol += AIB[pos];
        pos -= pos & -pos;
    }

    return sol;
}

///retin in intervale unde se afla fiecare element si fac query urile in ordine inversa
int nrinterv;
struct hlp
{
    int st, dr, val;
}interv[NMAX];

inline bool cmp(hlp a, hlp b)
{
    return a.dr > b.dr;
}

struct queryyy
{
    int st, dr, index;
    long long sol = 0;
}qq[NMAX];

inline bool cmp2(queryyy a, queryyy b)
{
    return a.dr > b.dr;
}

inline bool cmp3(queryyy a, queryyy b)
{
    return a.index < b.index;
}

inline void citire()
{
    fin >> n >> k >> q;
    int i;
    for(i = 1; i <= n; ++i)
        fin >> w[i];

    for(i = 1; i <= k; ++i)
        last[i] = n + 1;

    for(i = n; i > 0; --i)
    {
        interv[++nrinterv].st = i;
        interv[nrinterv].dr = last[w[i]];
        last[w[i]] = i;
        interv[nrinterv].val = w[i];
    }


    for(i = 1; i <= q; ++i)
        fin >> qq[i].st >> qq[i].dr, qq[i].index = i;

    sort(interv + 1, interv + 1 + nrinterv, cmp);
    sort(qq + 1, qq + 1 + q, cmp2);

    int intervalCurent = 1;
    for(i = 1; i <= q; ++i)
    {
        while(intervalCurent <= nrinterv && interv[intervalCurent].dr > qq[i].dr)
            update_aib(interv[intervalCurent].st, interv[intervalCurent].val), ++intervalCurent;
        qq[i].sol = query_aib(qq[i].dr) - query_aib(qq[i].st - 1);
        qq[i].sol %= MOD;
    }

    sort(qq + 1, qq + 1 + q, cmp3);

    for(i = 1; i <= q; ++i)
        fout << qq[i].sol << '\n';

}

int main()
{
    citire();


    return 0;
}