#include <bits/stdc++.h>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,m,k,i,j=1,v[100001],f[100001],d,s;
long long A[100001],sol[100001];
struct S{
    int st;
    int dr;
    int ind;
}q[100001];
bool cmp(S a, S b){
    return a.dr<=b.dr;
}
void update(int p,int val){
    for(;p<=n;p+=(p&-p))
        A[p]+=val;

}
long long query(int p){
    long long s=0;
    for(;p>=1;p-=(p&-p))
        s+=A[p];

    return s;
}
int main(){
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=1;i<=m;i++)
        fin>>q[i].st>>q[i].dr,q[i].ind=i;
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=n;i++){
        if(f[v[i]]!=0)
            update(f[v[i]],-1*v[i]);
        f[v[i]]=i;
        update(f[v[i]],v[i]);
        while(j<=m && q[j].dr==i){
            d=query(q[j].dr);//desc
            s=query(q[j].st-1);//scaz
            sol[q[j].ind]=d-s;//diferenta
            j++;
        }
    }
    for(i=1;i<=m;i++)
        fout<<sol[i]%666013<<'\n';
}