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