#include <bits/stdc++.h>
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
const int NMAX=100005,MOD=666013;///NMAX==MMAX
int n,k,m,start,finish;
vector<int>v,answer,aib,last_pos;
vector<pair<int,int>>queries[NMAX];
void update(int node,int value)
{
    for(; node<=n; node+=node&(-node))
        aib[node]=(aib[node]+value)%MOD;
}
int query(int node)
{
    int ans=0;
    for(; node>0; node-=node&(-node))
        ans=(ans+aib[node])%MOD;
    return ans;
}
int main()
{
    f>>n>>k>>m;
    v.resize(n+1);
    answer.resize(n+1);
    aib.resize(n+1);
    last_pos.resize(k+1);
    for(int i=1; i<=n; i++)
        f>>v[i];
    for(int i=1; i<=m; i++)
    {
        f>>start>>finish;
        queries[finish].push_back({start,i});
    }
    for(int i=1; i<=n; i++)
    {
        if(last_pos[v[i]]) /// we already encountered this value
            update(last_pos[v[i]],-v[i]);
        last_pos[v[i]]=i;
        update(i,v[i]);
        for(pair<int,int>q:queries[i])
            answer[q.second]=(query(i)-query(q.first-1)+MOD)%MOD;
    }
    for(int i=1; i<=m; i++)
        g<<answer[i]<<'\n';
    return 0;
}