#include <bits/stdc++.h>

using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const int NMAX=2e6+1, MOD=666013;
int n, k, m;
struct query
{
    int x, y, poz;
}q[NMAX];
long long result[NMAX+1];
int v[NMAX], aint[NMAX*4], last[NMAX];
bool cmp(query a, query b)
{
    return (a.y<=b.y);
}
void read_data()
{
    in>>n>>k>>m;
    for(int i=1; i<=n; i++)
        in>>v[i];
    for(int i=1; i<=m; i++)
    {
        in>>q[i].x>>q[i].y;
        q[i].poz=i;
    }
    sort(q+1, q+m+1, cmp);
}
void aint_update(int node, int st, int dr, int pos, int val)
{
    if(st==dr)
    {
        aint[node]=val;
        return;
    }
    int mijl=(st+dr)/2;
    if(pos<=mijl)
        aint_update(node*2, st, mijl, pos, val);
    else
        aint_update(node*2+1, mijl+1, dr, pos, val);
    aint[node]=( aint[node*2]+aint[node*2+1] )%MOD;
}
int aint_query(int node, int st, int dr, int stq, int drq)
{
    if(st>=stq && dr<=drq)
    {
        return aint[node];
    }
    int mijl=(st+dr)/2;
    long long sum=0;
    if(stq<=mijl)
        sum = (sum + aint_query(node*2, st, mijl, stq, drq))%MOD;
    if(drq>mijl)
        sum = (sum + aint_query(node*2+1, mijl+1, dr, stq, drq))%MOD;
    return sum%MOD;
}
int main()
{
    read_data();
    int id_q=1;
    for(int i=1; i<=n; i++)
    {
        if(last[v[i]]!=0)
        {
            aint_update(1, 1, n, last[v[i]], 0);
        }
        last[v[i]]=i;
        aint_update(1, 1, n, i, v[i]);
        //am luat in calcul elementul de pe pozitia i->vad ce query uri sunt interesate de el pana acum
        while(q[id_q].y==i)
        {
            if(id_q>m)
                break;
            result[q[id_q].poz]=aint_query(1, 1, n, q[id_q].x, q[id_q].y);
            id_q++;
        }
        if(id_q>m)
            break;
    }
    for(int i=1; i<=m; i++)
    {
        out<<result[i]<<'\n';
    }
}