#include <bits/stdc++.h>
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
const int NMAX=100005,MOD=666013;
int n,k,Q,pos,val,start,finish,sum,v[NMAX],last_pos[NMAX],SumTree[4*NMAX];
vector<int>ans;
vector<pair<int,int>>queries[NMAX];
void update(int node,int left,int right)
{
    if(left==right)///leaf
    {
        SumTree[node]=val;
        return;
    }
    int middle=(left+right)/2;
    if(pos<=middle)
        update(2*node,left,middle);///update left son
    else
        update(2*node+1,middle+1,right);///update right son
    SumTree[node]=(SumTree[2*node]+SumTree[2*node+1])%MOD;
}
void query(int node,int left,int right)
{
    if(start<=left && right<=finish)///verify if the current interval is inside the one from the query
    {
        sum=(sum+SumTree[node])%MOD;
        return;
    }
    int middle=(left+right)/2;
    if(start<=middle)
        query(2*node,left,middle);///query left son
    if(middle<finish)
        query(2*node+1,middle+1,right);///query right son
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n>>k>>Q;
    ans.resize(Q+1);
    for(int i=1; i<=n; i++)
        f>>v[i];
    for(int q=1; q<=Q; q++)
    {
        f>>start>>finish;
        queries[finish].push_back({start,q});
    }
    for(int i=1; i<=n; i++)
    {
        if(last_pos[v[i]]!=0)
        {
            pos=last_pos[v[i]];
            val=0;
            update(1,1,n);
        }
        pos=i;
        val=v[i];
        update(1,1,n);
        last_pos[v[i]]=i;
        for(pair<int,int> q:queries[i])
        {
            sum=0;
            start=q.first;
            finish=i;
            query(1,1,n);
            ans[q.second]=sum;
        }
    }
    for(int q=1; q<=Q; q++)
        g<<ans[q]<<'\n';
    return 0;
}