#include <cstdio>
#include <algorithm>
#define ub(x) (x&(-x))
#define MOD 666013
using namespace std;
struct awesome
{
    int st,dr,ord;
};
int n,k,m,v[100010],AIB[100010],x,y,ap[100010],sol[100010],i,j;
awesome q[100010];

inline bool cmp(awesome a,awesome b)
{
    if(a.dr<b.dr)  return true;
    if(a.dr==b.dr && a.st<=a.st)  return true;
    return false;
}

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

inline int sum(int poz)
{
    int i,s=0;
    for(i=poz;i>=1;i-=ub(i))
      s=(AIB[i]+s+MOD)%MOD;
   return s;
}

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d %d %d\n",&n,&k,&m);
    for(i=1; i<=n; ++i)
        scanf("%d\n",&v[i]);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d\n",&x,&y);
        q[i].st=x;
        q[i].dr=y;
        q[i].ord=i;
    }
    sort(q+1,q+m+1,cmp);j=1;

    for(i=1;i<=m;++i)
    {
        for(j;j<=q[i].dr;++j)
        {
            if(ap[v[j]])  upd(ap[v[j]],-v[j]);
            upd(j,v[j]);
            ap[v[j]]=j;
        }
        sol[q[i].ord]=(sum(q[i].dr)-sum(q[i].st-1)+MOD)%MOD;
    }
    for(i=1;i<=m;++i)
      printf("%d\n",sol[i]);
    return 0;
}