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