#include<cstdio>
#include<algorithm>
#define MAXN 100010
#define MOD 666013
using namespace std;
struct Query{
    int left;
    int right;
    int index;
};
Query query[MAXN];
bool Compare(Query a,Query b){
    return a.right<b.right;
}
int n,v[MAXN],position[MAXN],answer[MAXN],aib[MAXN];
void Update(int x,int value){
    for(x;x<=n;x=x+((x&(x-1))^x))
        aib[x]=(aib[x]+value)%MOD;
}
int Count(int x){
    int answer=0;
    for(x;x>0;x=x-((x&(x-1))^x))
        answer=(answer+aib[x])%MOD;
    return answer;
}
int main(){
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int k,m,i,j;
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=1;i<=m;i++){
        scanf("%d%d",&query[i].left,&query[i].right);
        query[i].index=i;
    }
    sort(query+1,query+m+1,Compare);
    j=1;
    for(i=1;i<=query[m].right;i++){
        if(position[v[i]]!=0)
            Update(position[v[i]],-v[i]);
        Update(i,v[i]);
        position[v[i]]=i;
        while(query[j].right==i){
            answer[query[j].index]=(Count(query[j].right)-Count(query[j].left-1)+MOD)%MOD;
            j++;
        }
    }
    for(i=1;i<=m;i++)
        printf("%d\n",answer[i]);
    return 0;
}