#include <cstdio>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, MOD = 666013;

struct Interval {
    int x, y, ind;
};

class MyComp {
    public :
        bool operator () (const Interval &A, const Interval &B) {
            return A.y < B.y;
        }
};

Interval I [N];
int n, k, m;
int last [N], a [N], ans [N];
long long aib [N];

inline int lsb (int x) {
    return x & (-x);
}

void update (int value, int i) {
    for (; i <= n; i = i + lsb (i))
        aib [i] = 1ll * aib [i] + value;
}

long long query (int i) {
    long long s = 0;
    for (;i >= 1; i = i - lsb (i))
        s = s + aib [i];
    return s;
}

int main () {
    int i, j;
    long long temp;

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

    scanf ("%d%d%d", &n, &k, &m);
    for (i = 1; i <= n; i ++)
        scanf ("%d", &a [i]);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &I [i].x, &I [i].y);
        I [i].ind = i;
    }
    sort (I + 1, I + 1 + m, MyComp ());
    j = 0;
    for (i = 1; i <= m; i ++) {
        while (j < I [i].y) {
            ++ j;
            if (last [a [j]])
                update (-a [j], last [a [j]]);
            update (a [j], j);
            last [a [j]] = j;
        }
        temp = query (I [i].y) - query (I [i].x - 1);
        temp = temp % MOD;
        ans [I [i].ind] = temp;
    }
    for (i = 1; i <= m; i ++)
        printf ("%d\n", ans [i]);
    return 0;
}