#include <bits/stdc++.h>
#define N 100005
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,m,k,a[N],aib[N],last[N],ap[N],sol[N];
vector<pair<int,int> > queries[N];
void Update(int poz,int val)
{
    for(int i=poz;i<=n;i+=i&-i)
        aib[i]+=val,aib[i]%=MOD;
}
int Suma(int poz)
{
    int s=0;
    for(int i=poz;i>0;i-=i&-i)
        s+=aib[i],s%=MOD;
    return s;
}
int 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];
        if(ap[a[i]]) last[i]=ap[a[i]];
        ap[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(last[r]) Update(last[r],-a[last[r]]),Update(r,a[r]);
        else 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;
}