#include <bits/stdc++.h>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int cst=200000+5,mod=666013;
int n,k,m,v[cst],ant[cst],aib[cst],sol[cst];
struct qry
{
    int i,j,poz;
} q[cst];
bool cmp(qry a,qry b)
{
    return a.j<b.j;
}
void upd(int p,int x)
{
    while(p<=n)
    {
        aib[p]=(aib[p]+x)%mod;
        p+=p&-p;
    }
}
int sum(int p)
{
    int s=0;
    while(p>0)
    {
        s=(s+aib[p])%mod;
        p-=p&-p;
    }
    return s;
}
int main()
{
    fin>>n>>k>>m;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    for(int i=1; i<=m; i++)
    {
        fin>>q[i].i>>q[i].j;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    int cnt=1;
    for(int j=1; j<=n; j++)
    {
        int x=v[j];
        if(ant[x])
            upd(ant[x],mod-x);
        upd(j,x);
        ant[x]=j;
        while(cnt<=m&&q[cnt].j==j)
        {
            sol[q[cnt].poz]=(sum(q[cnt].j)-sum(q[cnt].i-1)+mod)%mod;
            cnt++;
        }
    }
    for(int i=1; i<=m; i++)
        fout<<sol[i]<<'\n';
    return 0;
}