#include <fstream>
#include <algorithm>
#define MAXN 100005
#define NRM 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");

struct query{
    int x,y,ind;};

int n,k,m,v[MAXN],nxti[MAXN],nxt[MAXN],ord[MAXN];
long long sol[MAXN],aib[MAXN],xx;
query q[MAXN];

bool Comp(int a,int b){
    return nxt[a]>nxt[b];}
bool Comp2(query a,query b){
    return a.y>b.y;}

void update_aib(int a);
long long query_aib(int a);

int main()
{
    int i,j;
    f>>n>>k>>m;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=1;i<=k;i++)
        nxti[i]=n+1;
    for(i=n;i>=1;i--){
        nxt[i]=nxti[v[i]];
        nxti[v[i]]=i;
        ord[i]=i;}
    sort(ord+1,ord+n+1,Comp);
    for(i=1;i<=m;i++){
        f>>q[i].x>>q[i].y;
        q[i].ind=i;}
    sort(q+1,q+m+1,Comp2);
    j=1;
    for(i=1;i<=m;i++){
        for(j;nxt[ord[j]]>q[i].y;j++)
            update_aib(ord[j]);
        sol[q[i].ind]=query_aib(q[i].y)-query_aib((q[i].x)-1);}
    for(i=1;i<=m;i++)
        g<<sol[i]%NRM<<'\n';
    f.close();
    g.close();
    return 0;
}

void update_aib(int a){
    xx=1LL*v[a];
    while(a<=n){
        aib[a]+=xx;
        a+=(a&(-a));}}

long long query_aib(int a){
    long long S=0;
    while(a){
        S+=aib[a];
        a-=(a&(-a));}
    return S;}