#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int maxn=1e5+5;
const int mod=666013;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
struct query{
    int l,r,indi;
    bool operator<(const query& z){
        return r<z.r;
    }
};
int n,k,m;
int aint[4*maxn];
int v[maxn];
int last[maxn];
vector<query> queries;
void update(int nod,int l,int r,int poz,int val){
    if(l>poz || r<poz)return;
    if(l==poz && r==poz){
        aint[nod]+=val;
        return;
    }
    int mid=(l+r)/2;
    update(nod*2,l,mid,poz,val);
    update(nod*2+1,mid+1,r,poz,val);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
    aint[nod]%=mod;
}
int queryy(int nod,int l,int r,int st,int dr){
    if(l>dr || r<st)return 0;
    if(l>=st && r<=dr){
        return aint[nod];
    }
    int mid=(l+r)/2;
    return (queryy(nod*2,l,mid,st,dr)+queryy(nod*2+1,mid+1,r,st,dr))%mod;
}
int ans[maxn];
signed main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=m;i++){
        query z;
        z.indi=i;
        cin>>z.l>>z.r;
        queries.push_back(z);
    }
    sort(queries.begin(),queries.end());
    int r=0;
    for(auto elem:queries){
        while(r<elem.r){
            r++;
            update(1,1,n,last[v[r]],-v[r]);
            update(1,1,n,r,v[r]);
            last[v[r]]=r;
        }
        ans[elem.indi]=queryy(1,1,n,elem.l,elem.r)%mod;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}