#include <bits/stdc++.h>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
typedef long long ll;
const int lim=1e5+5;
const int mod=666013;
vector<pair<int,int> > u[lim];
int v[lim];
int ans[lim];
int last[lim];
int urm[lim];
vector<int> poz[lim];
int tree[4*lim];
void update(int nod,int l,int r,int poz)
{
    if(l==r)
    {
        tree[nod]=v[l]%mod;
        return ;
    }
    int med=(l+r)/2;
    if(poz<=med)
        update(2*nod,l,med,poz);
    else update(2*nod+1,med+1,r,poz);
    tree[nod]=(tree[2*nod]+tree[2*nod+1])%mod;
}
int query(int nod,int l,int r,int a,int b)
{
    if(a<=l and r<=b)
        return tree[nod];
    int med=(l+r)/2,ans1=0,ans2=0;
    if(a<=med) ans1=query(2*nod,l,med,a,b);
    if(b>med) ans2=query(2*nod+1,med+1,r,a,b);
    return (ans1+ans2)%mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    int n,k,m,x,y;
    in>>n>>k>>m;
    for(int i=1;i<=n;++i)
        in>>v[i];
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        u[y].push_back({x,i});
    }
    for(int i=n;i>=1;--i)
    {
        if(last[v[i]]==0)
            urm[i]=n+1;
        else urm[i]=last[v[i]];
        last[v[i]]=i;
        poz[urm[i]].push_back(i);
    }
    int cm=m;
    for(int i=n+1;i>=1 and cm>0;--i)
    {
        for(auto p:u[i])
            ans[p.second]=query(1,1,n,p.first,i),--cm;
        if(cm==0)
            break;
        for(int x:poz[i])
            update(1,1,n,x);
    }
    for(int i=1;i<=m;++i)
        out<<ans[i]<<'\n';
    return 0;
}