#include<bits/stdc++.h>

using namespace std;
#define MOD 666013
ifstream fin("distincte.in");
ofstream fout("distincte.out");
long long v[100005],lastpoz[100005],aib[100005],sol[100005],n;
struct kys
{
    long long st,dr,poz;
}a[100005];
bool compare(kys a, kys b)
{
    return a.dr<b.dr||a.dr==b.dr&&a.st<b.st;
}
void update(long long poz, long long val)
{
    long long i;
    for(i=poz;i<=n;i+=(i&-i))aib[i]+=val;
}
long long suma(long long poz)
{
    long long i,s=0;
    for(i=poz;i>=1;i-=(i&-i))s+=aib[i];
    return s;
}

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