#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

#define MOD 666013
#define lsb(x) (x&(-x))
#define NMAX 100007

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

int fen[NMAX] , x[NMAX] , pos[NMAX] , ans[NMAX];
priority_queue < pair < pair < int , int > , int > > aQ;
int N , M , K , i , lo , hi , crt;

void U(int pos,int x)
{
    if (pos == 0) return ;

    for (; pos <= N ; pos += lsb(pos))
    fen[pos] = (fen[pos] + x + MOD) % MOD;
}

int Q(int pos)
{
    int res = 0;

    for (; pos ; pos -= lsb(pos))
    res = (res + fen[pos]) % MOD;

    return res;
}

int main()
{

fin >> N >> K >> M;

for (i=1;i<=N;++i)
fin >> x[i];

for (i=1;i<=M;++i)
{
    fin >> lo >> hi;
    aQ.push({{-hi,-lo},i});
}

crt = 1;
while (aQ.size())
{
    hi = - aQ.top().first.first;
    lo = - aQ.top().first.second;
    i = aQ.top().second;
    aQ.pop();

    while (crt <= hi)
    {
        U(pos[x[crt]] , -x[crt]);
        pos[x[crt]] = crt;
        U(pos[x[crt]] , x[crt]);
        crt += 1;
    }

    ans[i] = (Q(hi) - Q(lo - 1) + MOD) % MOD;
}

for (i=1;i<=M;++i)
fout << ans[i] << '\n';

return 0;
}