#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)
{
    return x.y<y.y;
}
inline void update(int p,int v)
{
    for(; p<=n; p+=(p^(p&(p-1))))
    {
        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&(p-1))))
    {
        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;
}