#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int mod=666013;
int n,v[100010],aib[100010],poz[100010],rez[100010];
vector<pair<int,int> > q[100010];

void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=i&(-i))
    {
        aib[i]+=val;
        if(aib[i]>=mod) aib[i]-=mod;
        else if(aib[i]<0) aib[i]+=mod;
    }
}

int query(int poz)
{
    int sol=0;
    for(int i=poz;i>0;i-=i&(-i))
    {
        sol+=aib[i];
        if(sol>=mod) sol-=mod;
        else if(sol<0) sol+=mod;
    }
    return sol;
}

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int k,m,l,r;
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        q[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++)
    {
        if(poz[v[i]]>0) update(poz[v[i]],-v[i]);
        poz[v[i]]=i;
        update(i,v[i]);
        for(int j=0;j<q[i].size();j++)
        {
            rez[q[i][j].second]=query(i)-query(q[i][j].first-1);
            if(rez[q[i][j].second]<0) rez[q[i][j].second]+=mod;
        }
    }
    for(int i=1;i<=m;i++) printf("%d\n",rez[i]);
    return 0;
}