#include <fstream>
#include <algorithm>
#define MOD 666013
#define DIM 100001
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,k,m,v[DIM],f[DIM],aib[DIM],sol[DIM];
struct interval {
    int x,y,poz;
}q[DIM];

bool cmp(interval a,interval b) {
    if (a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

void update(int k,int val) {
    for (int i=k;i<=n;i+=(i&-i)) {
        aib[i]+=val;
        if (aib[i]>=MOD)
            aib[i]-=MOD;
        else
            if (aib[i]<0)
                aib[i]+=MOD;
    }
}

int query(int k) {
    int s=0;
    for (int i=k;i>=1;i-=(i&-i)) {
        s+=aib[i];
        if (s>=MOD)
            s-=MOD;
    }
    return s;
}

int main() {
    fin>>n>>k>>m;
    for (int i=1;i<=n;i++)
        fin>>v[i];
    for (int i=1;i<=m;i++) {
        fin>>q[i].x>>q[i].y;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    for (int i=1;i<=m;i++) {
        for (int j=q[i-1].y+1;j<=q[i].y;j++) {
            if (f[v[j]]!=0)
                update(f[v[j]],-v[j]);
            f[v[j]]=j;
            update(j,v[j]);
        }
        sol[q[i].poz]=query(q[i].y)-query(q[i].x-1);
        if (sol[q[i].poz]<0)
            sol[q[i].poz]+=MOD;
    }
    for (int i=1;i<=m;i++)
        fout<<sol[i]<<"\n";
    return 0;
}