#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
const int NMAX = 100002;
const int MOD = 666013;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

struct querys
{
    int l, r, ind;
}q[NMAX];
int v[NMAX]; ///vectorul de nr
int bucket[NMAX]; ///precalcularea bucketurilor
int ans[NMAX]; ///unde salvam rasp dupa indici
int f[NMAX]; ///frecv
int block, sum = 0, n;
bool cmp(querys x, querys y)
{
    if(bucket[x.l] != bucket[y.l])
        return x.l < y.l;
    return x.r < y.r;
}
void add(int i)
{
    if(i == 0)
        return;

    f[v[i]]++;
    if(f[v[i]] == 1)
        sum = (sum + v[i]) % MOD;
}
void removee(int i)
{
    if(i == 0)
        return;

    f[v[i]]--;
    if(f[v[i]] == 0)
    {
        int dif = sum - v[i];
        if(dif < 0)
            dif += MOD;
        sum = dif % MOD;
    }
}
int main()
{
    int m, k;
    cin >> n >> k >> m;
    block = sqrt(n);
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        bucket[i] = (i - 1) / block + 1;
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].ind = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int st = 0, dr = 0;
    for(int i = 1; i <= m; i++)
    {
        while(q[i].l < st)
            add(--st);
        while(dr < q[i].r)
            add(++dr);

        while(st < q[i].l)
            removee(st++);
        while(q[i].r < dr)
            removee(dr--);

        ans[q[i].ind] = sum;
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
    return 0;
}