#include<bits/stdc++.h>
#define maxN 100005
#define maxK 100005
#define MOD 666013
#define zeros(i) (i&(-i))
using namespace std;
int n,AIB[maxK],k,m,v[maxN],seen[maxK],sol[maxN],a,b,dq;
typedef struct QType
{
  int a,b,pos;
};
bool cmp(QType a,QType b)
{
    if(a.b<b.b) return 1;
    return 0;
}
void update(int pos,int x)
{
    for(int i=pos;i<=n;i+=zeros(i))
    {
        AIB[i]=(AIB[i]+x+MOD)%MOD;
    }
}
int solve(int pos)
{
    int s=0;
    for(int i=pos;i>=1;i-=zeros(i))
    {
        s=(s+AIB[i])%MOD;
    }
    return s%MOD;
}
QType query[maxN];
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        query[++dq]={a,b,i};
    }
    sort(query+1,query+m+1,cmp);
    int j=1;
    for(int i=1;i<=query[m].b;i++)
    {
        if(seen[v[i]])
        {
            update(seen[v[i]],-v[i]);
        }
        update(i,v[i]);
        seen[v[i]]=i;
        while(query[j].b==i)
        {
            sol[query[j].pos]=(solve(query[j].b)-solve(query[j].a-1)+MOD)%MOD;
            j++;
        }
    }
    for(int i=1;i<=m;i++) printf("%d\n",sol[i]);
    return 0;
}