#include<bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin ("distincte.in");
ofstream fout("distincte.out");
long long aib[100002];
long long n,lastpoz[100002],v[100002],sol[100002];

struct el
{
    long long st,dr,ord;
} q[100002];

bool cmp (const el &a,const el &b)
{
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}

void update(long long poz,long long val)
{
    long long i;
    for (i=poz;i<=n;i+=i&-i)
        aib[i]+=val;
}

long long query (long long poz)
{
    long long i;
    long long sum=0;
    for (i=poz;i>=1;i-=i&-i)
        sum+=aib[i];
    return sum;
}

int main()
{
    long long i,k,m,x,poz=1;
    fin>>n>>k>>m;
    for (i=1;i<=n;i++)
        {
            fin>>v[i];
            update(i,v[i]);
        }
    for (i=1;i<=m;i++)
        {
            fin>> q[i].st>>q[i].dr;
            q[i].ord=i;
        }
    sort(q+1,q+m+1,cmp);
    for (i=1;i<=m;i++)
    {
        while (poz<=q[i].dr)
        {
            if (lastpoz [v[poz]] !=0)
                update(lastpoz[v[poz]], -v[poz]);
            lastpoz[v[poz]]= poz;
            poz++;
        }
        sol[q[i].ord]=(query(q[i].dr)-query(q[i].st-1));
    }
    for (i=1;i<=m;i++)
        fout<<sol[i]%MOD<<'\n';

    return 0;
}