#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;

int N, M, K, i, j, v[VAL], P, nod;
int poz[VAL], last[VAL], ANS, A, B;
vector < pair <int, int> > AIB[VAL];

int ZERO(int X)
{
    return (X & (-X));
}

void Update(int nod)
{
    while (nod<=N)
    {
        AIB[nod].push_back({last[i], v[i]});
        nod+=ZERO(nod);
    }
}

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

void Query(int nod, int X)
{
    while (nod>0)
    {
        P=Binary_Search(nod, A);
        if (P>=0)
        {
            ANS+=X*AIB[nod][P].second;
            if (ANS>=MOD)
                ANS-=MOD;
            if (ANS<0)
                ANS+=MOD;
        }
        nod-=ZERO(nod);
    }
}

int main()
{
    fin >> N >> K >> M;
    for (i=1; i<=N; i++)
    {
        fin >> v[i];
        last[i]=poz[v[i]];
        poz[v[i]]=i;
        Update(i);
    }
    for (i=1; i<=N; i++)
    {
        nod=i;
        sort(AIB[nod].begin(), AIB[nod].end());
        for (j=1; j<AIB[nod].size(); j++)
        {
            AIB[nod][j].second+=AIB[nod][j-1].second;
            if (AIB[nod][j].second>=MOD)
                AIB[nod][j].second-=MOD;
        }
    }
    while (M>0)
    {
        M--;
        fin >> A >> B;
        ANS=0;
        Query(B, 1);
        Query(A-1, -1);
        fout << ANS << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}