#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

#define MOD 666013
#define int long long

pair<int,int> q[100001];
int p[100001];
int v[100001];
int rasp[100001];
int last[100001];
int aib[100001];
int n;

bool cmp(int a,int b){
    return q[a].second<q[b].second;
}

void update(int a,int b){
    if(a==0) return;
    for(;a<=n;a+=(a&-a)) aib[a]+=b;
}

int query(int a){
    int rasp=0;
    for(;a;a-=(a&-a)) rasp+=aib[a];
    return rasp;
}

signed main()
{
    int k,m,i,j;
    cin>>n>>k>>m;
    for(i=1;i<=n;++i) cin>>v[i];
    for(i=1;i<=m;++i){
        cin>>q[i].first>>q[i].second;p[i]=i;
    }
    sort(p+1,p+m+1,cmp);
    j=1;
    for(i=1;i<=m;++i){
        while(j<=q[p[i]].second){
           update(last[v[j]],-v[j]);
           update(j,v[j]);last[v[j]]=j;
           j++;
        }
        rasp[p[i]]=query(q[p[i]].second)-query(q[p[i]].first-1);
    }
    for(i=1;i<=m;i++)
        cout<<rasp[i]%MOD<<"\n";
    return 0;
}