#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int VAL=100005;
const int MOD=666013;

struct NOD
{
    vector < pair <int, int> > V;
};

NOD ARB[4*VAL];

int N, M, K, i, j, v[VAL], P;
int poz[VAL], last[VAL], ANS, A, B;

void Sortare(int nod, int be, int en)
{
    sort(ARB[nod].V.begin(), ARB[nod].V.end());
    for (int i=1; i<ARB[nod].V.size(); i++)
    {
        ARB[nod].V[i].second+=ARB[nod].V[i-1].second;
        if (ARB[nod].V[i].second>=MOD)
            ARB[nod].V[i].second-=MOD;
    }
}

void Initializare(int nod, int be, int en)
{
    if (be==en)
    {
        ARB[nod].V.push_back({last[be], v[be]});
        return;
    }
    int mid=(be+en) / 2, i;
    Initializare(2*nod, be, mid);
    Initializare(2*nod+1, mid+1, en);
    for (i=0; i<ARB[2*nod].V.size(); i++)
        ARB[nod].V.push_back(ARB[2*nod].V[i]);
    for (i=0; i<ARB[2*nod+1].V.size(); i++)
        ARB[nod].V.push_back(ARB[2*nod+1].V[i]);
    Sortare(2*nod, be, mid);
    Sortare(2*nod+1, mid+1, en);
}

int Binary_Search(int nod, int X)
{
    int be=0, en=ARB[nod].V.size()-1;
    int mid, P=-1;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (ARB[nod].V[mid].first<X)
        {
            P=mid;
            be=mid+1;
        }
        else
            en=mid-1;
    }
    return P;
}

void Query(int nod, int be, int en, int A, int B)
{
    if (A<=be && en<=B)
    {
        P=Binary_Search(nod, A);
        if (P>=0)
        {
            ANS+=ARB[nod].V[P].second;
            if (ANS>=MOD)
                ANS-=MOD;
        }
        return;
    }
    int mid=(be+en) / 2;
    if (max(be, A)<=min(mid, B))
        Query(2*nod, be, mid, A, B);
    if (max(mid+1, A)<=min(en, B))
        Query(2*nod+1, mid+1, en, A, B);
}

int main()
{
    fin >> N >> K >> M;
    for (i=1; i<=N; i++)
    {
        fin >> v[i];
        last[i]=poz[v[i]];
        poz[v[i]]=i;
    }
    Initializare(1, 1, N);
    Sortare(1, 1, N);
    while (M>0)
    {
        M--;
        fin >> A >> B;
        ANS=0;
        Query(1, 1, N, A, B);
        fout << ANS << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}