#include<algorithm>
#include<fstream.h>
#define input "distincte.in"
#define output "distincte.out"
#define Nmax 100005
#define Kmax 100005
#define mod 666013

long a[Nmax],x[2][Kmax],reel[Nmax],sum[Nmax];
int main()
	 {
	
    ifstream fin(input);
    ofstream fout(output);
    long i,k,n,m,t,u,ii,s,j;
    fin>>n>>k>>m;
   
    for (i=1;i<=n;i++)      
        {
        fin>>a[i];
        sum[i]=sum[i-1]+a[i];
        if (sum[i]>mod)
           sum[i]%=mod;
        if (x[0][a[i]]==0)
           {
           x[0][a[i]]++;
           x[1][a[i]]=i;                         
        
           }        
        else
            {
            reel[i]=x[1][a[i]];        
            x[1][a[i]]=i;
        
            }
        }
    for (i=1;i<=m;i++)
        {
        s=0;
        fin>>t>>u;
        if (sum[u]<sum[t])
           s=mod+sum[u]-sum[t-1];
        else
            s=sum[u]-sum[t-1];
        for (ii=t;ii<=u;ii++)
            {
            if (reel[ii]>=t)
               s-=a[ii];                 
            }
        while (s<0)
              s=s+mod;
        fout<<s<<"\n";
        }
      
    return 0;
    }