#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "distincte.in"
#define file_out "distincte.out"

#define lsb(x) ((x&(x-1))^x)
#define mod 666013
#define nmax 101000

int n,k,m;
int v[nmax];
int ind[nmax];
int poz[nmax];
int sol[nmax];
int x[nmax];
int y[nmax];
int aib[nmax];

void citire()
{
    int i;
    //freopen(file_in,"r",stdin);
    //freopen(file_out,"w",stdout);

    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", &x[i], &y[i]);
        ind[i]=i;
    }

}


int cmp(int a, int b)
{
    return y[a]<y[b];
}

void update(int poz, int val)
{

    int i;

    for (i=poz;i<=n;i+=lsb(i))
    {
        aib[i]+=val;
        if (aib[i]>=mod) aib[i]-=mod;
        if (aib[i]<0) aib[i]+=mod;
    }
}

int query(int poz)
{

    int i,sum=0;

    for (i=poz;i>=1;i-=lsb(i))
    {
        sum+=aib[i];
        if (sum>=mod) sum-=mod;
    }
    return sum;
}


void solve()
{

     int i,j;
     sort(ind+1,ind+m+1,cmp);

     j=1;

     for (i=1;i<=m;++i)
     {
         while(j<=y[ind[i]])
         {
             update(j,v[j]);
             if (poz[v[j]]!=0)
                 update(poz[v[j]],-v[j]);
             poz[v[j]]=j;
             j++;
         }

         sol[ind[i]]=query(y[ind[i]])-query(x[ind[i]]-1);
         if (sol[ind[i]]<0)
             sol[ind[i]]+=mod;

     }
     for (i=1;i<=m;++i) printf("%d\n", sol[i]);
}


int main()
{

    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;

}