# include <algorithm>
# include <cstdio>
using namespace std;

# define x first
# define y second

typedef long long ll;
const char *FIN = "distincte.in", *FOU = "distincte.out";
const int MAX = 100005, MOD = 666013;

pair <int, int> Q[MAX];
int N, M, K, V[MAX], prev[MAX], P[MAX];
ll aib[MAX], REZ[MAX];

void update (int nod, int val) {
    if (nod == 0) return ;
    for (; nod <= N; aib[nod] += val, nod += nod & -nod);
}

ll query (int nod) {
    ll sol;
    for (sol = 0; nod > 0; sol += aib[nod], nod -= nod & -nod);
    return sol;
}

struct comp {
    bool operator () (const int &A, const int &B) {
        return Q[A].y < Q[B].y;
    }
};

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d %d", &N, &K, &M);
    for (int i = 1; i <= N; ++i)
        scanf ("%d", V + i);
    for (int i = 1; i <= M; ++i)
        scanf ("%d %d", &Q[i].x, &Q[i].y), P[i] = i;
    sort (P + 1, P + M + 1, comp ());
    for (int i = 1, j = 1; i <= M; ++i) {
        for (; j <= Q[P[i]].y; update (prev[V[j]], -V[j]), update (j, V[j]), prev[V[j++]] = j);
        REZ[P[i]] = query (Q[P[i]].y) - query (Q[P[i]].x - 1);
    }
    for (int i = 1; i <= M; ++i)
        printf ("%lld\n", REZ[i] % MOD);
}