#include <cstdio>
#include <vector>
#define MOD 666013
using namespace std;
vector<pair<int,int> > G[100005];
FILE *f=fopen("distincte.in","r");
FILE *g=fopen("distincte.out","w");
int N,M,K;
int last[100005];
int AIB[100005];
int V[100005];
int Q[100005];
int adun(int a,int b)
{
    a+=b;
    if(a>=MOD)a-=MOD;
    return a;
}
int scad(int a,int b)
{
    a-=b;
    if(a<0)a+=MOD;
    return a;
}
void u(int pos,int val)
{
    for(;pos<=N;pos+=(-pos)&pos)
        AIB[pos]=adun(AIB[pos],val);
}
int q(int pos)
{
    int sum=0;
    for(;pos;pos-=(-pos)&pos)
        sum=adun(sum,AIB[pos]);
    return sum;
}
int main()
{
    fscanf(f,"%d%d%d",&N,&K,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d",&V[i]);
    }
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fscanf(f,"%d %d",&x,&y);
        G[y].push_back({x,i});
    }
    for(int i=1;i<=N;i++)
    {
        if(last[V[i]])
        {
            u(last[V[i]],MOD-V[i]);
        }
        last[V[i]]=i;
        u(i,V[i]);
        for(auto it:G[i])
        {
            Q[it.second]=scad(q(i),q(it.first-1));
        }
    }
    for(int i=1;i<=M;i++)
        fprintf(g,"%d\n",Q[i]);
    fclose(f);
    fclose(g);
    return 0;
}