#include <vector>
#include <queue>
#include <fstream>
#include <iostream>
#include <climits>
#include <algorithm>

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

const int LMAX = 100005;
const int MOD = 666013;
int v[LMAX], p = 1, sol[LMAX];
long long active[LMAX*3];
struct query{
    int first, second, ind;
}q[LMAX];
int lastpos[LMAX];

bool cmp(query x, query y) {
    return x.second < y.second;
}

void update(int nod, int st, int dr) {
    if (st == dr) {
        active[nod] = v[st];
    }
    else {
        int m = ((st + dr)>>1);
        if (p <= m) {
            update(nod*2, st, m);
        }
        else {
            update(nod*2 + 1, m + 1, dr);
        }
        active[nod] = active[nod*2] + active[nod*2 + 1];
    }
}

void deactivate(int nod, int st, int dr, int pos) {
    if (st == dr) {
        active[nod] = 0;
    }
    else {
        int m = ((st + dr)>>1);
        if (pos <= m) {
            deactivate(nod*2, st, m, pos);
        }
        else {
            deactivate(nod*2 + 1, m + 1, dr, pos);
        }
        active[nod] = active[nod*2] + active[nod*2 + 1];
    }
}

int sum(int nod, int st, int dr, int qs, int qd) {
    if (st == qs && dr == qd) {
        return active[nod]%MOD;
    }
    else {
        int m = ((st + dr)>>1);
        if (qd <= m) {
            return sum(nod*2, st, m, qs, qd)%MOD;
        }
        else if (qs > m) {
            return sum(nod*2 + 1, m + 1, dr, qs, qd)%MOD;
        }
        else {
            return (sum(nod*2, st, m, qs, m)%MOD + sum(nod*2 + 1, m + 1, dr, m + 1, qd)%MOD)%MOD;
        }
    }
}

int main() {
    int n, m, k, i;
    fin>>n>>k>>m;
    for (i = 1; i <= n; i++) {
        fin>>v[i];
    }
    for (i = 0; i < m; i++) {
        fin>>q[i].first>>q[i].second;
        q[i].ind = i;
    }
    sort(q, q+m, cmp);
    for (i = 0; i < m; i++) {
        while (p <= q[i].second) {
            update(1, 1, n);
            if (lastpos[v[p]]) {
                deactivate(1, 1, n, lastpos[v[p]]);
            }
            lastpos[v[p]] = p;
            p++;
        }
        sol[q[i].ind] = sum(1,1,n, q[i].first, q[i].second);
    }
    for (i = 0; i < m; i++) {
        fout<<sol[i]<<endl;
    }

    fin.close();
    fout.close();

    return 0;
}