#include <bits/stdc++.h>
#define MOD 666013

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n, k, Q, r, a[100003], fr[100003];
struct Interogare
{
    int x, y, ind, raspuns;
}v[100003];
bool Compara1(Interogare A, Interogare B)
{
    if (A.x / r == B.x / r)
        return A.y < B.y;
    return A.x / r < B.x / r;
}

bool Compara2(Interogare A, Interogare B)
{
    return A.ind < B.ind;
}

int main()
{
    int i, j, x, y, x2, y2, s;
    fin >> n >> k >> Q;
    r = sqrt(n);
    for (i = 1; i <= n; i++)
        fin >> a[i];
    for (i = 1; i <= Q; i++)
    {
        fin >> v[i].x >> v[i].y;
        v[i].ind = i;
    }
    sort(v + 1, v + Q + 1, Compara1);
    s = 0;
    for(i = v[1].x;i <= v[1].y;i++)
    {
        if(fr[a[i]] == 0)
            s = (s + a[i]) % MOD;
        fr[a[i]]++;
    }
    v[1].raspuns = s;
    for(j = 2;j <= Q;j++)
    {
        x = v[j - 1].x;
        y = v[j - 1].y;
        x2 = v[j].x;
        y2 = v[j].y;
        for(i = x - 1;i >= x2;i--)
        {
            if(fr[a[i]] == 0)
                s = (s + a[i]) % MOD;
            fr[a[i]]++;
        }
        for(i = x;i < x2;i++)
        {
            if(fr[a[i]] == 1)
                s = (s - a[i] + MOD) % MOD;
            fr[a[i]]--;
        }
        for(i = y + 1;i <= y2;i++)
        {
            if(fr[a[i]] == 0)
                s = (s + a[i]) % MOD;
            fr[a[i]]++;
        }
        for(i = y;i > y2;i--)
        {
            if(fr[a[i]] == 1)
                s = (s - a[i] + MOD) % MOD;
            fr[a[i]]--;
        }
        v[j].raspuns = s;
    }
    sort(v + 1, v + Q + 1, Compara2);
    for(i = 1;i <= Q;i++)
        fout << v[i].raspuns << "\n";
    return 0;
}