#include <iostream>
#include <fstream>
#include <vector>

#define Nmax 100005
#define MOD 666013

using namespace std;

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

struct qry
{
    int st,poz;
};
vector <qry> L[Nmax];

int N,poz[Nmax],a[Nmax];
int sol[Nmax],aib[Nmax];

inline void Update(int poz,int val)
{
    int i;
    for(i=poz;i>0;i-=(i&(-i)))
        aib[i]+=val;
}

inline int Query(int poz)
{
    int i,sol=0;
    for(i=poz;i<=N;i+=(i&(-i)))
        sol=(sol+aib[i])%MOD;
    return sol;
}

int main()
{
    int i,x,y,K,M;
    vector <qry>::iterator it;
    qry w;
    fin >> N >> K >> M;
    for(i=1;i<=N;++i)
        fin >> a[i];
    for(i=1;i<=M;++i)
    {
        fin >> x >> y;
        w.st=x;
        w.poz=i;
        L[y].push_back(w);
    }
    for(i=1;i<=N;++i)
    {
        Update(i,a[i]);
        Update(poz[a[i]],-a[i]);
        poz[a[i]]=i;
        for(it=L[i].begin();it!=L[i].end();++it)
            sol[it->poz]=Query(it->st);
    }
    for(i=1;i<=M;++i)
        fout << sol[i] << '\n';
    return 0;
}