#include <bits/stdc++.h>

using namespace std;


ifstream fin("distincte.in");
ofstream fout("distincte.out");

int n,k,m;
int v[100005];
int last[100005];
int nxt[100005];
int aib[100005];
int sol[100005];
pair <pair<int, int>, int> intrebari[100005];

const int MOD = 666013;


void update(int poz, int valoare)
{
    while(poz <= n)
    {
        aib[poz] = (aib[poz] + valoare) % MOD;
        poz += ( poz & (-poz) ) ;
    }
}

int query(int poz)
{
    int s = 0;

    while(poz > 0)
    {
        s = (s + aib[poz]) % MOD;
        poz -= ( poz & (-poz) );
    }

    return s;
}


int main()
{

    fin>>n>>k>>m;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        if (last[v[i]] == 0)
            update(i, v[i]);
        else
            nxt[ last [ v[i] ] ] = i;

        last[v[i]] = i;
    }

    for(int i=1; i<=m; i++)
    {
        fin>>intrebari[i].first.first>>intrebari[i].first.second;
        intrebari[i].second = i;
    }

    sort(intrebari+1, intrebari+1+m);

    int j=1;
    for(int i=1; i<=n; i++)
    {
        while (intrebari[j].first.first == i)
        {
            sol[intrebari[j].second] = query(intrebari[j].first.second);
            ++j;
        }

        update(i, -v[i]);
        if (nxt[i])
            update(nxt[i], v[i]);
    }

    for (int i = 1; i <= m; ++i)
        fout << sol[i] << "\n";

    return 0;

}