#include <cstdio>
#include <algorithm>
using namespace std;
 
 
const int maxn = 100005;
const int mod = 666013;
struct que {
    int x;
    int y;
    int pos;
};
que q[maxn];
 
int aib[maxn], n, k, m, v[maxn], preg[maxn], sol[maxn];
 
int cmp(que a, que b)
{
    return a.y < b.y;
}
 
int lsb(int x)
{
    return (x & (x - 1)) ^ x;
}
 
int query(int a)
{
    int i, sol = 0;
    for(i = a; i >= 1; i -= lsb(i))
        sol = (sol + aib[i]) % mod;
    return sol;
}
 
void update(int a, int b)
{
    int i;
    for(i = a; i <= n; i += lsb(i))
        aib[i] = (aib[i] + b) % mod;
}
 
 
int main()
{
    int i, j;
    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", &v[i]);
    for(i = 1; i <= m; ++i) {
        scanf("%d %d", &q[i].x, &q[i].y);
        q[i].pos = i;
    }
    sort(q + 1, q + m + 1, cmp);
    for(i = 1; i <= m; ++i) {
        for(j = q[i - 1].y + 1; j <= q[i].y; ++j) {
            if(preg[v[j]] != 0)
                update(preg[v[j]], -v[j] + mod);
            update(j, v[j]);
            preg[v[j]] = j;
        }
        sol[q[i].pos] = query(q[i].y) - query(q[i].x - 1);
        if(sol[q[i].pos] < 0)
            sol[q[i].pos] += mod;
    }
    for(i = 1; i <= m; ++i)
        printf("%d\n", sol[i]);
    return 0;
}