#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin ("distincte.in");
ofstream cout ("distincte.out");
const int mod=666013;
long long bit[100005];
int last[100005],n;
int a[100005];
int rasp[100005];
void update (int poz,int val)
{
    while(poz<=n)
    {
        bit[poz]=(bit[poz]+val)%mod;
        poz=poz+(poz&-poz);
    }
}
int  pq(int poz)
{
    long long suma=0;
    while(poz)
    {
        suma=(suma+bit[poz])%mod;
        poz=poz-(poz&-poz);
    }
    return suma;
}
struct str
{
    int st,dr,poz;
};
str e[100005];
bool cmp (str a,str b)
{
    if(a.dr !=b.dr)
    {
        return a.dr<b.dr;
    }
            return a.st<b.st;
}
int main()
{
    int i,j,k,l,curr,m;
    cin>>n>>k>>m;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<=m;i++)
    {
        cin>>e[i].st>>e[i].dr;
        e[i].poz=i;
    }
    sort(e+1,e+m+1,cmp);
    curr=1;
    for(i=1;i<=m;i++)
    {
        while(curr<=e[i].dr)
        {
            if(last[a[curr]]==0)
            {
                update(curr,a[curr]);
                last[a[curr]]=curr;
                curr++;
            }
            else
            {
                update(last[a[curr]],-a[curr]);
                last[a[curr]]=curr;
                update(curr,a[curr]);
                curr++;
            }
        }
        rasp[e[i].poz]=pq(e[i].dr)-pq(e[i].st-1);
        if(rasp[e[i].poz]<0)
        {
            rasp[e[i].poz]+=mod;
        }
    }
    for(i=1;i<=m;i++)
    {
        cout<<rasp[i]<<'\n';
    }
    return 0;
}