#include <bits/stdc++.h>

#define DIM 100000
#define DIM 666013

#define int long long

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

//ifstream f("filesmodel.in");
//ofstream g("filesmodel.out");

int n,k,m;

int v[DIM+5];

int u[DIM+5];

int aib[DIM+5];

int sol[DIM+5];

struct info{
    int st;
    int dr;
    int id;
}q[DIM+5];

int query(int poz){
    int sol = 0;
    for(int i=poz;i>=1;i-=(i&-i)){
        sol+=aib[i];
    }
    return sol;
}

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

bool cmp(info a,info b){
    return a.dr<b.dr;
}

signed main(){

    f>>n>>k>>m;

    for(int i=1;i<=n;i++){
        f>>v[i];
    }

    for(int i=1;i<=m;i++){
        f>>q[i].st>>q[i].dr;
        q[i].id = i;
    }
    sort(q+1,q+m+1,cmp);

    int j = 1;
    for(int i=1;i<=n;i++){

        if(u[v[i]] != 0){
            update(u[v[i]],-v[i]);
        }
        update(i,v[i]);

        u[v[i]] = i;

        while(j<=m && q[j].dr == i){
            sol[q[j].id] = query(q[j].dr) - query(q[j].st-1);
            j++;
        }
    }

    for(int i=1;i<=m;i++){
        g<<sol[i]%MOD<<'\n';
    }

    return 0;
}