#include <algorithm>
using namespace std;

#define MOD 666013
#define DIM 100005

struct numar {int st,dr,x;} a[DIM],v[DIM];
int urm[DIM],aib[DIM];
int n,m,k;

int lsb (int x)
{
    return x&(x-1)^x;
}

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

int query (int poz)
{
    int sum;

    for (sum=0; poz; poz-=lsb (poz))
        sum=(sum+aib[poz])%MOD;

    return sum;
}

void read ()
{
    int i;

    scanf ("%d%d%d",&n,&k,&m);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d",&a[i].x);
        a[i].st=urm[a[i].x];
        a[i].dr=n+1;
        a[a[i].st].dr=i;
        urm[a[i].x]=i;
        if (!a[i].st)
            update (i,a[i].x);
    }
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&v[i].st,&v[i].dr);
        v[i].x=i;
    }
}

int cmp1 (const numar &a,const numar &b)
{
    return a.st<b.st;
}

int cmp2 (const numar &a,const numar &b)
{
    return a.x<b.x;
}

void solve ()
{
    int i,j;

    sort (v+1,v+m+1,cmp1);
    for (j=1, i=1; i<=n; ++i)
    {
        for ( ; v[j].st==i; ++j)
            v[j].dr=(query (v[j].dr)-query (v[j].st-1))%MOD;
        update (i,-a[i].x);
        update (a[i].dr,a[i].x);
    }
    sort (v+1,v+m+1,cmp2);
}

void print ()
{
    int i;

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

int main ()
{
    freopen ("distincte.in","r",stdin);
    freopen ("distincte.out","w",stdout);

    read ();
    solve ();
    print ();

    return 0;
}