#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxN 100002
#define mod 666013
using namespace std;
int n, i, j, m, k, v[maxN], used[maxN], sol[maxN], arb[maxN * 4];
struct Query
{
    int x;
    int y;
    int z;
} a[maxN];
inline void update(int node, int l, int r, int p, int val)
{
    if (l > r)
        return;
    if (l == r)
    {
        arb[node] = val % mod;
        return ;
    }
    int lson = 2 * node, rson = lson + 1, mid = (l + r) >> 1;
    if (p <= mid)
        update(lson, l, mid, p, val);
    else
        update(rson, mid + 1, r, p, val);
    arb[node] = (arb[lson] + arb[rson]) % mod;
}
inline int query(int node, int l, int r, int x, int y)
{
    if (l > r)
        return 0;
    if (l >= x && r <= y)
        return arb[node];
    int lson = 2 * node, rson = lson + 1, mid = (l + r) >> 1;
    if (y <= mid)
        return query(lson, l, mid, x, y);
    else
    {
        if (x > mid)
            return query(rson, mid + 1, r, x, y);
        else
            return (query(lson, l, mid, x, mid) + query(rson, mid + 1, r, mid + 1, y)) % mod;
    }

    return 0;
}
int cmp(const Query p, const Query q)
{
    return p.y < q.y;
}
void read()
{
    freopen("distincte.in", "r", stdin);
    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", &a[i].x, &a[i].y);
        a[i].z = i;
    }
}
void solve()
{
    sort(a + 1, a + m + 1, cmp);
    for (i = 1; i <= m; ++ i)
    {
        for (j = a[i - 1].y + 1; j <= a[i].y; ++ j)
        {
            if (used[v[j]])
                update(1, 1, n, used[v[j]], 0);
            update(1, 1, n, j, v[j]);
            used[v[j]] = j;
        }
        sol[a[i].z] = query(1, 1, n, a[i].x, a[i].y);
    }
}
void write()
{
    freopen("distincte.out", "w", stdout);
    for (i = 1; i <= m; ++ i)
        printf("%d\n", sol[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}