#include <fstream>
#include <cstdio>
#include <algorithm>
#define LUIJI  100010
#define MOD 666013
#define ub(x) (x&(-x))
using namespace std;
int v[LUIJI],i,k,n,m,j;
int ok[LUIJI],aib[LUIJI],sol[LUIJI];
struct reus{int x,y,z;};
reus op[LUIJI];
bool crs(reus A,reus B){
    if(A.y==B.y)return (A.x<B.x);
    return (A.y<B.y);}

    void upd(int poz, int val){
        int i;
        for(i=poz;i<=n;i+=ub(i))
        aib[i]=(val+aib[i]+MOD)%MOD;}

        int calc(int poz){
            int i,s=0;
            for(i=poz;i;i-=ub(i))
            s=(s+aib[i]+MOD)%MOD;
            return s;}

int main(){
    freopen("distincte.in","r",stdin);
    ofstream g ("distincte.out");
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
        for(i=1;i<=m;++i){
            scanf("%d%d",&op[i].x,&op[i].y);
            op[i].z=i;}
            sort(op+1,op+m+1,crs);
            j=1;
            for(i=1;i<=m;++i){
                for(;j<=op[i].y;++j){
                if(ok[v[j]])upd(ok[v[j]],-v[j]);
                upd(j,v[j]);
                ok[v[j]]=j;}
                sol[op[i].z]=(calc(op[i].y)-calc(op[i].x-1)+MOD)%MOD;
                }
                for(i=1;i<=m;++i)
                g<<sol[i]<<'\n';
                return 0;}