#include <bits/stdc++.h>
#define DIM 100001
#define MOD 666013
#define int long long
using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct query{
    int poz, st, dr;
}q[DIM];

int n, k, m;
int i, j;
int aib[DIM], v[DIM], f[DIM], ans[DIM];

bool comp(query a, query b){
    return a.dr<b.dr;
}

void update(int pos, int val){
    for(int i=pos; i<=n; i+=(i&-i))
        aib[i]+=val;
}

int query(int pos){
    int sum=0;
    for(int i=pos; i>0; i-=(i&-i))
        sum+=aib[i];
    return sum;
}

int32_t 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].poz=i;
    }
    sort(q+1, q+m+1, comp);
    for(i=1; i<=m; i++){
        while(j<q[i].dr){
            j++;
            if(f[v[j]])
                update(f[v[j]],-v[j]);
            f[v[j]]=j;
            update(j,v[j]);
        }
        ans[q[i].poz]=(query(q[i].dr)-query(q[i].st-1))%MOD;
    }
    for(i=1; i<=m; i++)
        fout<<ans[i]<<"\n";
}