#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");
struct elem
{
long long st,dr,p;
};

elem q[100001];

long long aib[100001],n,v[100001],poz[100001],rez[100001];


inline bool cmp(const elem &a, const elem &b)
{
if (a.dr==b.dr) return a.st<b.st;
return a.dr<b.dr;
}

void update(long long poz, long long add)
{
for (int i=poz;i<=n;i+=i&-i) aib[i]+=add;
}

long long querysum(long long poz)
{long long sol=0;
for (int i=poz;i>=1;i-=i&-i) sol+=aib[i];
return sol;
}

int main()
{int j,k,m,i;
f>>n>>k>>m;
for (i=1;i<=n;i++) {f>>v[i]; update(i,v[i]); }
for (i=1;i<=m;i++) {f>>q[i].st>>q[i].dr; q[i].p=i; }
sort(q+1,q+m+1,cmp);

j=1;
for (i=1;i<=m;i++) {while (j<=q[i].dr) {if (poz[v[j]]!=0) update(poz[v[j]],v[j]*-1);
                                            poz[v[j]]=j;
                                            j++;
                                           }

                        rez[q[i].p]=querysum(q[i].dr)-querysum(q[i].st-1);
                        }
for(int i=1;i<=m;i++) g<<rez[i]%MOD<<'\n';
}