#include <bits/stdc++.h>
#define Nmax 100002
#define Mod 666013
#define lsb(x) (x & -x)
FILE *fin  = freopen("distincte.in", "r", stdin);
FILE *fout = freopen("distincte.out", "w", stdout);

using namespace std;
int n, k, m, aib[Nmax], use[Nmax], v[Nmax], sol[Nmax];
struct query
{
    int x;
    int y;
    int p;
} q[Nmax];
bool cmp(const query a, const query b)
{
    return a.y < b.y;
}
void update(int pos, int val)
{
    for(int i = pos; i <= n; i += lsb(i))
        aib[i] += val;
}
int sum(int pos)
{
    int s = 0;
    for(int i = pos; i >= 1; i -= lsb(i))
        s = (s + aib[i]) % Mod;
    return s;
}
void read()
{
    int i;
    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].p = i;
    }
}
void solve()
{
    int i = 0, j = 1;
    sort(q + 1, q + m + 1, cmp);
    for(i = q[0].y + 1; i <= q[m].y; ++ i)
    {
        if(use[v[i]])
            update(use[v[i]], -v[i]);
        update(i, v[i]);
        use[v[i]] = i;

        /// query
        if(i == q[j].y)
        {
            sol[q[j].p] = sum(q[j].y) - sum(q[j].x - 1);
            if(sol[q[j].p] < 0) sol[q[j].p] += Mod;
            ++ j;
        }
    }
}
void write()
{
    for(int i = 1; i <= m; ++ i)
        printf("%d\n", sol[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}