#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
int n,K,q,A[100005],buc;
const int mod = 666013;
struct idx
{
    int st,dr,i;
};
idx Q[100005];
int F[100005];
long long ans[100005];
struct process
{
    long long ans=0;
    void add(int x)
    {
        F[A[x]]++;
        if(F[A[x]]==1)
            ans+=A[x];
    }
    void rem(int x)
    {
        F[A[x]]--;
        if(F[A[x]]==0)
            ans-=A[x];
    }
    long long get()
    {
        return ans%mod;
    }
};
int main()
{
    cin>>n>>K>>q;
    for(int i=1;i<=n;i++)
        cin>>A[i];
    for(int i=1;i<=q;i++)
        cin>>Q[i].st>>Q[i].dr,Q[i].i=i;
    buc=sqrt(n);
    sort(Q+1,Q+q+1,[](idx a,idx b)
    {
        return a.st/buc<b.st/buc || (a.st/buc==b.st/buc && a.dr<b.dr);
    });
    process mo;
    int mo_st=1,mo_dr=0;
    for(int i=1;i<=q;i++)
    {
        auto [st,dr,idx]=Q[i];
        while(mo_dr<dr)
        {
            mo_dr++;
            mo.add(mo_dr);
        }
        while(mo_dr>dr)
        {
            mo.rem(mo_dr);
            mo_dr--;
        }
        while(mo_st>st)
        {
            mo_st--;
            mo.rem(mo_st);
        }
        while(mo_st<st)
        {
            mo.add(mo_st);
            mo_st++;
        }
        ans[idx]=mo.get();
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
    return 0;
}