#include<stdio.h>
#include<algorithm>
using namespace std;

#define ll long long
#define MOD 666013

struct inter
{
    int x,y,z;
    ll sol;
};
inter q[100005];
int v[100005],n,m,k,inc;
int urm[100005],f[100005];
ll AIB[100005];

void update(int x,int val)
{
    for (; x <= n; x += x^(x-1)&x)
        AIB[x] += val;
}

ll query(int x)
{
    ll S = 0;
    for (; x; x -= x^(x-1)&x)
        S += AIB[x];
    return S;
}

int cmp(inter a,inter b)
{
    return (a.y<b.y);
}

int cmp2(inter a,inter b)
{
    return (a.z<b.z);
}

int main ()
{
    int i;
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        update(i,v[i]);
    }
    for(i=1;i<=n;i++)
    {
        urm[i]=f[v[i]];
        f[v[i]]=i;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].x,&q[i].y);
        q[i].z=i;
    }
    sort(q+1,q+m+1,cmp);
    inc=1;
    for(i=1;i<=n;i++)
    {
        if(urm[i])
            update(urm[i],-v[i]);
        while(inc<=m && q[inc].y==i)
        {
            q[inc].sol=query(q[inc].y)-query(q[inc].x-1);
            inc++;
        }
    }
    sort(q+1,q+m+1,cmp2);
    for(i=1;i<=m;i++)
        printf("%lld\n",(q[i].sol)%MOD);
    return 0;
}