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

ifstream f("distincte.in");
ofstream g("distincte.out");

struct interval
{
    long long st,dr,index;
}q[SIZE];

long long aib[SIZE],v[SIZE],sol[SIZE],p[SIZE],n;

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

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

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

int main()
{
    long long i,m,k,l;
    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].index=i;
    }
    sort(q+1,q+m+1,cmp);
    i=1;
    for(l=1;l<=m;l++)
    {
        while(i<=q[l].dr)
        {
            if(p[v[i]]!=0)update(p[v[i]],-v[i]);
            p[v[i]]=i;
            i++;
        }
        sol[q[l].index]=querysum(q[l].dr)-querysum(q[l].st-1);
    }

    for(i=1;i<=m;i++)g<<sol[i]%MOD<<'\n';
    return 0;
}