//
//  main.cpp
//  distincte
//
//  Created by Andrada Minca on 04.11.2025.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("distincte.in");
//ofstream cout("distincte.out");
struct kk
{
    int st;
    int dr;
    int order;
};
vector<long long> aib;
int lsb(int x)
{
    return (x&(-x));
}
void update(int x,int add)
{
    for(int i=x;i<aib.size();i+=lsb(i))
    {
        aib[i]+=add;
    }
}
long long query(int x)
{
    long long sum=0;
    for(int i=x;i>0;i-=lsb(i))
    {
        sum+=aib[i];
        sum%=666013;
    }
    return sum%666013;
}
int bs(long long s)
{
    int ans=0;
    long long sum=0;
    for(int pas=(1<<17);pas>0;pas/=2)
    {
        if(ans+pas+1<aib.size()&&sum+aib[ans+pas]<s)
        {
            ans+=pas;
            sum+=aib[ans];
            sum%=666013;
        }
    }
    if(query(ans+1)==s)
    {
        return ans+1;
    }
    else return -1;
}
bool cmp(kk a, kk b)
{
    return a.st<b.st;
}
int main()
{
    int n,k,m;
    cin>>n>>k>>m;
    aib.resize(n+1);
    vector<int>v(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    vector<kk>q(m);
    for(int i=0;i<m;i++)
    {
        cin>>q[i].st>>q[i].dr;
        q[i].order=i;
    }
    sort(q.begin(),q.end(),cmp);
    vector<int>fr(k+1);
    //cerr<<"linia 75";
    vector<long long> ans(m);
    int ind=m-1;
    for(int i=n;i>0;i--)
    {
        if(fr[v[i]]!=0)update(fr[v[i]],-v[i]);
        update(i,v[i]);
        fr[v[i]]=i;
        //cout<<q[ind].st<<" ";
        while(ind>=0&&i==q[ind].st)
        {
            //cout<<query(q[ind].dr)<<'\n';
            ans[q[ind].order]=query(q[ind].dr);
            ind--;
        }
        
    }
    for(int i=0;i<m;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}