#include <fstream>
#include <algorithm>
using namespace std;
class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};
ifstream fin ("distincte.in");
OutParser fout("distincte.out");
long long n,m,k,i,st,V[100003],sol[100003],A[400003],f[100003];
struct elem
{
    long long x,y,ind;
}Q[100003];
const long long MOD=666013;
void update(int poz,int val)
{
    for(poz;poz<=n;poz+=(poz&(-poz)))
        A[poz]+=val;
}
long long query(int poz)
{
    long long S=0;
    for(poz;poz;poz-=(poz&(-poz)))
        S+=A[poz];
    return S;
}
int main()
{
    fin>>n>>k>>m;
    for(i=1;i<=n;i++)
        fin>>V[i];
    for(i=1;i<=m;i++)
    {
        fin>>Q[i].x>>Q[i].y;
        Q[i].ind=i;
    }
    sort(Q+1,Q+m+1,[](elem a,elem b){return a.y<b.y;});
    st=1;
    for(i=1;i<=m;i++)
    {
        while(st<=Q[i].y)
        {
            if(f[V[st]])
                update(f[V[st]],-V[st]);
            f[V[st]]=st;
            update(st,V[st]);
            st++;
        }
        sol[Q[i].ind]=query(Q[i].y)-query(Q[i].x-1)%MOD;
        if(sol[Q[i].ind]<0)
            sol[Q[i].ind]+=MOD;
    }
    for(i=1;i<=m;i++)
        fout<<sol[i]%MOD<<"\n";
    return 0;
}