#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int a[100005],sol[100005],L,R=-1,n,k,q,sq,fr[100005];
long long s;
struct Queries
{
    int l,r,ind;
};Queries Q[100005];
bool cmp(Queries a, Queries b)
{
    if(a.l/sq == b.l/sq) return a.r<b.r;
    return a.l/sq < b.l/sq;
}
void Add(int x)
{
    fr[x]++;
    if(fr[x]==1)s+=x%MOD;
}
void Erase(int x)
{
    fr[x]--;
    if(fr[x]==0)s-=x%MOD;
}
void Mo(int i)
{
    while(L>Q[i].l)
    {
        L--;
        Add(a[L]);
    }
    while(R<Q[i].r)
    {
        R++;
        Add(a[R]);
    }
    while(L<Q[i].l)
    {
        Erase(a[L]);
        L++;
    }
    while(R>Q[i].r)
    {
        Erase(a[R]);
        R--;
    }
    sol[Q[i].ind]=s%MOD;
}
/**
6 3 2
1 2 2 1 3 1
2 5
1 4
*/

int main()
{
    int i;
    fin>>n>>k>>q;
    sq=sqrt(n);
    for(i=1;i<=n;i++)fin>>a[i];
    for(i=1;i<=q;i++)
    {
        fin>>Q[i].l>>Q[i].r;
        Q[i].ind=i;
    }
    sort(Q+1,Q+q+1,cmp);
    for(i=1;i<=q;i++)Mo(i);
    for(i=1;i<=q;i++)
        fout<<sol[i]<<'\n';
    return 0;
}