#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int NMAX = 100000+5;
const int MMAX = 100000+5;
const int MOD = 666013;

int N,K,M;
int V[NMAX];
int ante[NMAX];
int AIB[NMAX];
int st[MMAX],dr[MMAX];
int Q[MMAX];
int Sol[MMAX];

void update(int x,int val)
{
    for(int i=x; i<=N; i+=i&(-i))
        AIB[i]=(AIB[i]+MOD+val)%MOD;
}

int query(int x)
{
    int ans=0;
    for(int i=x; i; i-=i&(-i))
        ans=(ans+AIB[i])%MOD;
    return ans;
}

inline bool cmp(const int &x,const int &y)
{
    return dr[x]<dr[y];
}

int main()
{
    int i,j;

    fin>>N>>K>>M;

    for(i=1; i<=N; i++)
        fin>>V[i];

    for(i=1; i<=M; i++)
    {
        fin>>st[i]>>dr[i];
        Q[i]=i;
    }

    sort(Q+1,Q+M+1,cmp);

    for(i=1; i<=M; i++)
    {
        for(j=dr[Q[i-1]]+1; j<=dr[Q[i]]; j++)
        {
            if(ante[V[j]]) update(ante[V[j]],-V[j]);
            update(j,V[j]);
            ante[V[j]]=j;
        }
        Sol[Q[i]]=(query(dr[Q[i]])-query(st[Q[i]]-1)+MOD)%MOD;
    }

    for(i=1; i<=M; i++)
        fout<<Sol[i]<<'\n';

    return 0;
}