#include <bits/stdc++.h>
#define N 100005
#define MOD 666013
#define ll long long
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,m,k,a[N],last[N],ap[N];
ll aib[N],sol[N];
vector<pair<ll,ll> > queries[N];
void Update(int poz,ll val)
{
    for(int i=poz;i<=n;i+=i&-i)
        aib[i]+=val,aib[i]%=MOD;
}
ll Suma(int poz)
{
    ll s=0;
    for(int i=poz;i>0;i-=i&-i)
        s+=aib[i],s%=MOD;
    return s;
}
ll Query(int x,int y)
{
    return (Suma(y)-Suma(x-1)+MOD)%MOD;
}
int main()
{
    int i,l,r;
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];//last[a[i]]=i;
       /// cout<<last[i]<<" ";
    }
    for(i=1;i<=m;i++)
       fin>>l>>r,queries[r].push_back({l,i});
    for(r=1;r<=n;r++)
    {
        if(ap[a[r]]) last[r]=ap[a[r]];
        ap[a[r]]=r;if(last[r]) Update(last[r],-a[last[r]]);
        Update(r,a[r]);

        for(auto x:queries[r])
        {
            l=x.first;
            int q=x.second;
            sol[q]=Query(l,r);
        }
    }
    for(i=1;i<=m;i++) fout<<sol[i]<<"\n";
    return 0;
}