#include <bits/stdc++.h>

using namespace std;

long long s[100055];

int n,m,k,x[100055];

long long mod=666013;

struct el
{
    int x,y,i;
};
el v[100055];

long long r[100055];

bool ord(const el & a,const el & b)
{
    if(a.y<b.y || a.y==b.y && a.x<=b.x)
    {
        return true;
    }
    return false;
}

int u[100005];

void up(int k,int val)
{
    int i=k;
    while(i<=n)
    {
        s[i]=(s[i]+val)%mod;
        i+=i&-i;
    }
}

long long sm(int k)
{
    int i=k;
    long long sum=0;
    while(i>=1)
    {
        sum=(sum+s[i])%mod;
        i-=i&-i;
    }
    return sum;
}

int main()
{
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");
    cin>>n>>k>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>x[i];
    }
    for(int i=1;i<=m;++i)
    {
        cin>>v[i].x>>v[i].y;
        v[i].i=i;
    }
    sort(v+1,v+m+1,ord);
    int in=1;
    for(int i=1;i<=n;++i)
    {
        if(u[x[i]]!=0)
        {
            up(u[x[i]],(-1)*x[i]);
        }
        u[x[i]]=i;
        up(i,x[i]);
        while(in<=m && v[in].y==i)
        {
            r[v[in].i]=(sm(v[in].y)-sm(v[in].x-1)+mod)%mod;
            ++in;
        }
    }
    for(int i=1;i<=m;++i)
    {
        cout<<r[i]<<"\n";
    }
    return 0;
}