#include <fstream>
#include <vector>
#include <algorithm>
#define mod 666013
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
struct numar
{
    int st,dr,poz;
} q[100005];
long long aib[100005],n,m,k,v[100005],sol[100005],ap[100005];
void update(int p,long long val)
{
    for(int i=p; i<=n; i+=(-i&i))
        aib[i]+=val;
}
long long query(int p)
{
    long long s=0;
    for(int i=p; i>=1; i-=(-i&i))
        s+=aib[i];
    return s;
}
int cmp(numar a,numar b)
{
    return a.dr<b.dr;
}
int main()
{
    cin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    for(int i=1; i<=m; i++)
    {
        cin>>q[i].st>>q[i].dr;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    int j=0;
    for(int i=1; i<=m; i++)
    {
        while(j<q[i].dr)
        {
            j++;
            if(ap[v[j]]==0)
                ap[v[j]]=j,update(j,v[j]);
            else if(ap[v[j]])
            {
                update(ap[v[j]],-v[j]);
                ap[v[j]]=j;
                update(j,v[j]);
            }
        }
        sol[q[i].poz]=(query(q[i].dr)-query(q[i].st-1)+mod)%mod;
    }
    for(int i=1; i<=m; i++)
        cout<<sol[i]<<'\n';
    return 0;
}