#include<fstream>
#include<algorithm>
#define x first
#define y second
# define ll long long
using namespace std;
const int maxn=100005;
const int mod=666013;
ifstream f("distincte.in");
ofstream g("distincte.out");
pair<int,int> q[maxn];
bool comp(int a,int b)
{
    return q[a].y<q[b].y;
}
int n,m,i,x,a[maxn],last[maxn],k,p[maxn],j;
ll aib[maxn],ans[maxn];
inline void update(int x,int y)
{
    if(x==0) return;
    for(;x<=n;x+=x&-x) aib[x]+=y;
}
inline ll query(int x)
{
    ll 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,comp);
    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";
}