#include <bits/stdc++.h>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
typedef long long ll;
const ll lim=1e5+4,mod=666013;
vector<pair<ll,ll> > upd[lim];
ll n,t,q,l,r;
ll tree[lim];
ll last[lim];
ll ans[lim];
ll v[lim];
void add(ll k,ll x)
{
    while(k<=n)
    {
        tree[k]=(tree[k]+x);
        k+=k&-k;
    }
}
ll sum(ll k)
{
    ll ans=0;
    while(k)
    {
        ans=(ans+tree[k]);
        k-=k&-k;
    }
    return ans;
}
int main()
{
    in>>n>>t>>q;
    for(ll i=1;i<=n;++i)
        in>>v[i];
    for(ll i=1;i<=q;++i)
    {
        in>>l>>r;
        upd[r].push_back({l,i});
    }
    for(ll i=1;i<=n;++i)
    {
        if(last[v[i]]) add(last[v[i]],-v[i]);
        add(i,v[i]); last[v[i]]=i;
        if(!upd[i].size()) continue;
        ll dr=sum(i);
        for(auto t:upd[i])
            ans[t.second]=(dr-sum(t.first-1));
    }
    for(ll i=1;i<=q;++i)
        out<<ans[i]%mod<<'\n';
    return 0;
}