#include <fstream>
#include <algorithm>

#define In "distincte.in"
#define Out "distincte.out"
#define Nmax 100010
#define MOD 666013
#define sf(x) ((x)&(-(x)))

using namespace std;

struct query
{
    int st, dr, ind;
    bool operator < (const query &A) const
    {
        if(A.dr==dr)
            return A.st>st;
        return A.dr>dr;
    }
};

int AIB[Nmax];//arborele indexat binar
///AIB[i] = suma elementelor distincte din intervalul [i-2^k+1,i]
int a[Nmax];//elementele vectorulu initial
int ult[Nmax];//ult[i] = cea mai din drepta pozitie aflata in stanga lui v[i] la pasul k
int sol[Nmax];
int N,M,k;//k este pentru pargurgerea vecorului initial
query q[Nmax];//setul de intrebari

inline void Citire()
{
    ifstream f(In);
    f >> N>> M >> M;
    int i;
    for(i = 1;i <= N;i++)
    {
        f >> a[i];
        ult[a[i]] = N+1;
    }
    for(i = 1; i<= M ;i++)
    {
        f>> q[i].st >> q[i].dr;
        q[i].ind = i;
     }
     sort(q+1,q+M+1);
}

inline void Update(int poz,int val)
{
    for(;poz <= N;poz+=sf(poz))
    {
        AIB[poz] += val;
        AIB[poz] %= MOD;
        if(AIB[poz]<0)
            AIB[poz] += val;
    }
}

inline int Query(int poz)
{
    int S;
    for(S = 0;poz;poz -= sf(poz))
    {
        S += AIB[poz];
        S %= MOD;
    }
    return S;
}

inline void Rezolvare()
{
    int i,s;
    for(i = 1,k = 1;i <= M; i++)
    {
        for(;k<=q[i].dr;k++)
        {
            Update(ult[a[k]],-a[k]);//scot din aib pe a[k] daca acesta mai apare odata la pasii precedenti
            Update(k,a[k]);
            ult[a[k]] = k;
        }
        s = Query(q[i].dr)- Query(q[i].st-1);
        if(s < 0)
            s += MOD;
        sol[q[i].ind] = s;
    }
}

inline void Afisare()
{
    ofstream g(Out);
    for(int i = 1;i <= M;i++)
        g<<sol[i]<<"\n";
    g.close();
}

int main()
{
    Citire();
    Rezolvare();
    Afisare();
    return 0;
}