#include <fstream>
#define NM 100005
#define ub(x) (x&(-x))
#define mod 666013
#include <algorithm>

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

int n,m,sol[NM],x[NM],ap[NM],aib[NM],i,j;
struct str{int f,s,o;};
str q[NM];

inline bool CMP(str x,str y)
{
    if(x.s==y.s) return (x.f<y.f);
    return (x.s<y.s);
}
inline void upd(int poz,int val)
{
   for(int i=poz;i<=n;i+=ub(i)) aib[i]=(aib[i]+val+mod)%mod;
}
inline int Q(int poz)
{
    int nr=0;for(int i=poz;i;i-=ub(i)) nr=(nr+aib[i]+mod)%mod;return nr;
}
int main()
{
    f>>n>>m>>m;
    for(i=1;i<=n;++i) f>>x[i];
    for(i=1;i<=m;++i)
    {
        f>>q[i].f>>q[i].s;q[i].o=i;
    }
    sort(q+1,q+m+1,CMP);j=1;

    for(i=1;i<=m;++i)
    {
        for(;j<=q[i].s;++j)
        {
            if(ap[x[j]]) upd(ap[x[j]], -x[j]);
            upd(j, x[j]);
            ap[x[j]]=j;
        }
        sol[q[i].o]=(Q(q[i].s)-Q(q[i].f-1)+mod)%mod;
    }
    for(i=1;i<=m;++i) g<<sol[i]<<'\n';
    return 0;
}