#include <fstream>
#include <algorithm>
#define bit(i) i&(-i)
#define nMax 100001
#define mMax 100001
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n, m, k, v[nMax], Sol[nMax], aib[nMax], last[nMax];
struct queries
{
    int st;
    int dr;
    int poz;
}Q[mMax];
bool cmp(queries o, queries p)
{
    return o.dr<p.dr;
}
void upDate(int poz, int val)
{
    if(poz==0)
        return;
    for(int i=poz;i<=n;i+=bit(i))
    {
        aib[i]+=val;
        if(aib[i]>=MOD)
            aib[i]-=MOD;
        if(aib[i]<0)
            aib[i]+=MOD;
    }
}
int query(int poz)
{
    int nr=0;
    for(int i=poz;i>=1;i-=bit(i))
    {
        nr+=aib[i];
        if(nr>=MOD)
            nr-=MOD;
    }
    return nr;
}
void read()
{
    fin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int i=1;i<=m;i++)
    {
        fin>>Q[i].st>>Q[i].dr;
        Q[i].poz=i;
    }
}
void solve()
{
    int j=0;
    sort(Q+1, Q+m+1, cmp);
    for(int i=1;i<=m;i++)
    {
        while(j<=Q[i].dr)
        {
            upDate(last[v[j]], -v[j]);
            upDate(j, v[j]);
            last[v[j]]=j;
            j++;
        }
        Sol[Q[i].poz]=(query(Q[i].dr)-query(Q[i].st-1)+MOD)%MOD;

    }
}
void write()
{
    for(int i=1;i<=m;i++)
        fout<<Sol[i]<<'\n';
}
int main()
{
    read();
    solve();
    write();
    return 0;
}