#include <bits/stdc++.h>
using namespace std;
ifstream fcin("distincte.in");
ofstream fcout("distincte.out");

const int N = 1e5 + 5;
int r = 316;
int mod = 666013;
int aib[N], fr[N], v[N], n, m, k;
long long suma;
/**
6 3 2
1 2 2 1 3 1
1 4
2 5
*/

struct Interogare
{
    int a, b, ind, sol;
} q[N];

bool comp1(Interogare a, Interogare b)
{
    if (a.a / r == b.a / r)
        return a.b < b.b;
    return a.a / r < b.a / r;
}
bool comp2(Interogare a, Interogare b)
{
    return a.ind < b.ind;
}

void Update(int poz, int x)
{
    while (poz <= n)
    {
        aib[poz] += x;
        poz += (poz & -poz);
    }
}

int Query(int poz)
{
    int suma = 0;
    while (poz > 0)
    {
        suma +=aib[poz];
        poz -= (poz & -poz);
    }
    return suma;
}

int main()
{
    int st, dr, x;
    fcin >> n >> k >> m;
    for (int i = 1; i <= n; i++)
        fcin >> v[i];
    for (int i = 1; i <= m; i++)
    {
        fcin >> q[i].a >> q[i].b;
        q[i].ind = i;
    }
    sort(q + 1, q + m + 1, comp1);
    st = q[1].a;
    dr = q[1].b;
    for (int i = st; i <= dr; i++)
    {
        x = v[i];
        if (fr[x] == 0)
            suma += x;
        fr[x]++;
    }
    q[1].sol = suma % mod;
    for (int j = 2; j <= m; j++)
    {
        while (st < q[j].a)
        {
            x = v[st];
            fr[x]--;
            if (fr[x] == 0)
                suma -= x;
            st++;
        }
        while (st > q[j].a)
        {
            st--;
            x = v[st];
            if (fr[x] == 0)
                suma += x;
            fr[x]++;
        }
        while (dr < q[j].b)
        {
            dr++;
            x = v[dr];
            if (fr[x] == 0)
                suma += x;
            fr[x]++;
        }
        while (dr > q[j].b)
        {
            x = v[dr];
            fr[x]--;
            if (fr[x] == 0)
                suma -= x;
            dr--;
        }
        q[j].sol = suma % mod;
    }
    sort(q + 1, q + m + 1, comp2);
    for (int i = 1; i <= m; i++)
        fcout << q[i].sol << '\n';

    return 0;
}