#include <bits/stdc++.h>
using namespace std;
ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

const int MAXN=100010;
const int MOD=666013;
typedef long long ll;

int n,k,m,v[MAXN],last[MAXN];
ll aib[MAXN],ans[MAXN];;
struct query{
    int l,r,pos;
}q[MAXN];

bool comp (query a, query b){
    if (a.r==b.r) return a.l<b.l;
    return a.r<b.r;
}

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

long long Suma (int pos){
    long long rez=0;
    for (int i=pos;i>=1;i-=(i&(-i)))
        rez+=aib[i];
    return rez;
}

int main()
{
    fin >>n>>k>>m;
    for (int i=1;i<=n;++i){
        fin >>v[i];
        Update (i,v[i]);
    }
    for (int i=1;i<=m;++i){
        fin >>q[i].l>>q[i].r;
        q[i].pos=i;
    }
    sort (q+1,q+m+1,comp);
    int crt=1;
    for (int i=1;i<=m;++i){
        while (crt<=q[i].r){
            if (last[v[crt]])
                Update (last[v[crt]],-v[crt]);
            last[v[crt]]=crt;
            ++crt;
        }
        ans[q[i].pos]=Suma (q[i].r)-Suma (q[i].l-1);
        ans[q[i].pos]%=MOD;
    }
    for (int i=1;i<=m;++i){
        fout <<ans[i]<<'\n';
    }
    fin.close ();
    fout.close ();
    return 0;
}