#include<bits/stdc++.h>
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int n,k,m,v[100002],buk;
int frq[100002];
long long ans[100002];
const int mod = 666013;
long long sum;
struct qu
{
    int L, R, pi;
};
qu a[100002];
bool cmp(qu a, qu b)
{
    if(a.L/buk != b.L/buk)
        return a.L/buk < b.L/buk;
    return a.R<b.R;
}
void add(int pos)
{
    int val = v[pos];
    ++frq[val];
    if(frq[val]==1)
        sum += val;
}
void scoate(int pos)
{
    int val = v[pos];
    --frq[val];
    if(frq[val]==0)
        sum -= val;
}
int main()
{
    f>>n>>k>>m;
    buk=sqrt(n);
    for(int i=1;i<=n;++i)
        f>>v[i];
    for(int i=1;i<=m;++i)
        f>>a[i].L>>a[i].R, a[i].pi=i;
    sort(a+1, a+m+1, cmp);
    int L=1;
    int R=0;
    for(int i=1;i<=m;++i)
    {
        while(L>a[i].L)
            add(--L);
        while(R<a[i].R)
            add(++R);
        while(L<a[i].L)
            scoate(L++);
        while(R>a[i].R)
            scoate(R--);
        ans[a[i].pi]=sum%mod;
    }
    for(int i=1;i<=m;++i)
        g<<ans[i]<<'\n';
    return 0;
}