#include <fstream>
#include <algorithm>

using namespace std;

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

const int Nmax = 100005, NR = 666013;
int n,aib[Nmax],v[Nmax],last[Nmax],ll[Nmax];
struct question{
    int st;
    int dr;
    int pos;
    int ans;
} q[Nmax];
bool cmp1(question a, question b){
    return(a.dr<b.dr);
}
bool cmp2(question a, question b){
    return(a.pos<b.pos);
}
int mod(int x){
    int r = x%NR;
    if(r>=0)
        return r;
    r+=NR;
    return r;
}
void update(int x, int y){
    for(int i=x;i<=n;i+=(i&(-i))){
        aib[i]+=y;
        aib[i] = mod(aib[i]);
    }
}
int query(int x){
    if(x == 0)
        return 0;
    int s = 0;
    for(int i=x;i>0;i-=(i&(-i))){
        s+=aib[i];
        s = mod(s);
    }
    return s;
}

int main()
{
    int k,m,i,j;
    fin >> n >> k >> m;
    for(i=1;i<=n;i++){
        fin >> v[i];
        update(i,v[i]);
    }
    for(i=1;i<=m;i++){
        fin >> q[i].st >> q[i].dr;
        q[i].pos = i;
    }
    sort(q+1,q+m+1,cmp1);
    for(i=1;i<=k;i++)
        ll[i] = -1;
    for(i=1;i<=n;i++)
        last[i] = -1;
    for(i=1;i<=n;i++){
        if(ll[v[i]]!=-1)
            last[i] = ll[v[i]];
        ll[v[i]] = i;
    }
    j = 1;
    for(i=1;i<=m;i++){
        while(j<=q[i].dr){
            if(last[j]!=-1)
                update(last[j],-v[j]);
            j++;
        }
        q[i].ans = query(q[i].dr)-query(q[i].st-1);
        q[i].ans = mod(q[i].ans);
    }
    sort(q+1,q+m+1,cmp2);
    for(i=1;i<=m;i++)
        fout << q[i].ans << '\n';
    return 0;
}