#include <cstdio>
#include <vector>
#define Nmax 100005
#define MOD 666013

using namespace std;

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;
    freopen ("distincte.in","r",stdin);
    freopen ("distincte.out","w",stdout);
    scanf("%d%d%d", &N,&K,&M);
    for(i=1;i<=N;++i)
        scanf("%d", &a[i]);
    for(i=1;i<=M;++i)
    {
        scanf("%d%d", &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)
        printf("%d\n", sol[i]);
    return 0;
}