#include <fstream>
#include<algorithm>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
long long aib[100002],n,k,m,w[100001],fr[100001],sol[100001];
struct elem
{
    int a,b,poz;
}v[100001];
bool cmp(elem x,elem y)
{
    return x.a<y.a||(x.a==y.a&&x.b<y.b);
}
int lsb(int x)
{
    return x&(-x);
}
long long query(int x)
{
    long long sum=0;
    while(x)
    {
        sum+=aib[x];
        sum%=mod;
        x-=lsb(x);
    }
    return sum;
}
void update(int x,int val)
{
    for(int i=x;i<=n;i+=lsb(i))
        {
            aib[i]+=val;
            if(aib[i]<0)
                aib[i]=mod;
            aib[i]%=mod;
        }
}
int main()
{
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        {
            fin>>w[i];
        }
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].a>>v[i].b;
        v[i].poz=i;
    }
    sort(v+1,v+m+1,cmp);
    int k=1;
    for(int i=1;i<=m;i++)
    {
        for(;k<=v[i].b;k++)
        {
            if(fr[w[k]])
            update(fr[w[k]],-w[k]);
            fr[w[k]]=k;
            update(k,w[k]);
        }
        sol[v[i].poz]=query(v[i].b)-query(v[i].a-1);
        if(sol[v[i].poz]<0)
            sol[v[i].poz]=mod;
        sol[v[i].poz]%=mod;

    }
    for(int i=1;i<=m;i++)
        fout<<sol[i]%mod<<"\n";
    return 0;
}