#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];
int 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)
        {
            --L;
            add(L);
        }
        while(R<a[i].R)
        {
            ++R;
            add(R);
        }
        while(L<a[i].L)
        {
            ++L;
            scoate(L);
        }
        while(R>a[i].R)
        {
            --R;
            scoate(R);
        }
        long long p=sum%mod;
        ans[a[i].pi]=p;
    }
    for(int i=1;i<=m;++i)
        g<<ans[i]<<'\n';
    return 0;
}