#include<fstream>
#include<algorithm>
#define x first
#define y second

using namespace std;

const char iname[]="distincte.in";
const char oname[]="distincte.out";
const int maxn=100005;
const int mod=666013;

ifstream f(iname);
ofstream g(oname);

pair<int,int> q[maxn];
bool fcomp(int a,int b)
{
    return q[a].y<q[b].y;
}

int n,m,i,x,a[maxn],last[maxn],k,p[maxn],j;
long long aib[maxn];
long long ans[maxn];

inline void update(int x,int y)
{
    if(x==0)
        return;
    for(;x<=n;x+=x&-x)
        aib[x]+=y;
}

inline long long query(int x)
{
    long long s=0;
    for(;x;x-=x&-x)
        s+=aib[x];
    return s;
}

int main()
{
    f>>n>>k>>m;
    for(i=1;i<=n;++i)
        f>>a[i];
    for(i=1;i<=m;++i)
        f>>q[i].x>>q[i].y,p[i]=i;
    sort(p+1,p+m+1,fcomp);
    j=1;
    for(i=1;i<=m;++i)
    {
        while(j<=q[p[i]].y)
            update(last[a[j]],-a[j]),update(j,a[j]),last[a[j]]=j,++j;
        ans[p[i]]=query(q[p[i]].y)-query(q[p[i]].x-1);
    }
    for(i=1;i<=m;++i)
        g<<ans[i]%mod<<"\n";
}