#include<stdio.h> 
#include <algorithm>   
using namespace std;   

struct querry
{ 
    int x, y, c; 
}; 

int n, i, j, k, m, v[100005], t[100005];
long long rez[100005], x[100005], sol[100005]; 
querry s[100100];   

int lsb(int x)
{  
	return x ^ (x & (x - 1));    
}  

bool cmp(querry a, querry b)
{ 
  if(a.y < b.y)
	return 1;    
  else    
	return 0;
}

void update(int a, int b)
{
  while(a <= n) 
  {
	x[a] = x[a] + b;    
	a += lsb(a);  
	}    
}

long long question(int a)
{
  long long r = 0;  
  while(a)
  {   
	r = (r + x[a]) % 666013;  
	a -= lsb(a);     
  }       
  return r; 
}

int main()
{
  freopen("distincte.in","r",stdin);     
  freopen("distincte.out","w",stdout);
  scanf("%d%d%d", &n, &k, &m);
  for(i = 1; i <=n ; i ++)
	scanf("%d", &v[i]);  
  for(i = 1; i <= m; i ++) 
  { 
	scanf("%d%d", &s[i].x, &s[i].y);  
	s[i].c = i;
  }     
  sort(s + 1, s + m + 1, cmp);
  for(i = 1; i <= m; i ++) 
  {
	for(j = s[i-1].y + 1; j <= s[i].y; j ++)
	{      
	  if(t[v[j]] != 0) 
		update(t[v[j]], -v[j]);
	  update(j, v[j]);   
	  t[v[j]] = j;  
	}       
	rez[i] = question(s[i].y) - question(s[i].x - 1);
	if(rez[i] < 0) 
	  rez[i] += 666013;
  }       
  for(i = 1; i <= m; i ++)  
	sol[s[i].c] = rez[i];    
  for(i = 1; i <= m; i ++)   
    printf("%lld\n", sol[i]);   
  return 0; 
}