#include<fstream>
#include<algorithm>
#define MOD 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int i,n,m,j,aib[100100],a[100100],pred[100100],sol[100100];
struct que{int x,y,ind;};
que q[100100];
inline bool cmp(que x,que y)
{
    if(x.x==y.x)
    return x.y>y.y;
    return x.x>y.x;
}
inline void update(int p,int v)
{
    for(;p<=n;p+=((p^((p-1)&p))))
    {
        aib[p]+=v;
        aib[p]%=MOD;
        if(aib[p]<0)
        aib[p]+=MOD;
    }
}
inline int query(int p)
{
    int rez=0;
    for(;p;p-=(p^((p-1)&p)))
    {
        rez+=aib[p];
        rez%=MOD;
    }
    return rez;
}
int main()
{
    f>>n>>m>>m;
    for(i=1;i<=n;++i)
    {
        f>>a[i];
        pred[a[i]]=n+1;
    }
    for(i=1;i<=m;++i)
    {
        f>>q[i].x>>q[i].y;
        q[i].ind=i;
    }
    sort(q+1,q+m+1,cmp);
    for(i=1,j=1;i<=m;++i)
    {
        for(;j<=q[i].y;++j)
        {
            update(pred[a[j]],-a[j]);
            update(j,a[j]);
            pred[a[j]]=j;
        }
        sol[q[i].ind]=query(q[i].y)-query(q[i].x-1);
        if(sol[q[i].ind]<0)
        sol[q[i].ind]+=MOD;
    }
    for(i=1;i<=m;++i)
    g<<sol[i]<<'\n';
    return 0;
}