#include <fstream>
#include <algorithm>
#include <vector>
#define ub(i) i&(-i)
#define nmax 100005
#define mod 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
struct query{int x;int y;int poz;};
query q[nmax];
vector <int> p[nmax];
int t[nmax];
long long aib[nmax];
int v[nmax],n,m,k;
int sol[nmax];


inline bool cmp(const query &a, const query &b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
int aibsum(int poz)
{
    int sum=0;
    for (;poz;poz-=ub(poz)) {
        sum+=aib[poz];
        if (sum>mod)
            sum-=mod;
    }
    return sum;
}
void aibadd(int poz,int val)
{
    for (;poz<=nmax;poz+=ub(poz))
        aib[poz]+=1LL*val;
}
int main()
{
    int i,j,val;
    f>>n>>k>>m;
    for (i=1;i<=n;i++)
        f>>v[i];
    for (i=1;i<=m;i++) {
        f>>q[i].x>>q[i].y;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    for (i=1;i<=n;i++)
        p[v[i]].push_back(i);
    for (i=1;i<=n;i++)
        v[i]=0;
    for (i=1;i<=k;i++)
        if (p[i].size()) {
            v[p[i][0]]=i;
            aibadd(p[i][0],i);
        }
    j=1;
    for (i=1;i<=m;i++) {
        while (j<q[i].x) {
            val=v[j];
            t[val]++;
            if (t[val]<p[val].size()) {
                v[p[val][t[val]]]=val;
                aibadd(p[val][t[val]],val);
            }
            aibadd(j,-v[j]);
            v[j]=0;
            j++;
        }
        sol[q[i].poz]=aibsum(q[i].y)%mod;
    }
    for (i=1;i<=m;i++)
        g<<sol[i]<<'\n';

    return 0;
}