// n*m+parsare citire :P
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "distincte.in"
#define out "distincte.out"
#define modulo 666013
#define dim 100001

int a[dim];
int sel[dim];
int n, m, k;
int sum=0;

int Query(int,int);

int main()
{
    int x, y;
    
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fscanf(fin,"%d%d%d", &n, &k, &m);
    fscanf(fin,"\n");
    
    char linie[19];
    int j, aux;
    
    for ( int i = 1; i <= n; i++ )
    {
        fgets(linie,18,fin);
        j = 0;
        aux=0;
        while ( linie[j] >= '0' && linie[j] <= '9' )
        {
              aux *= 10;
              aux += (int)linie[j]-48;
              j++;
        }
        a[i] = aux;
    }
    
    int t;
    
    for ( int i = 1; i <= m; i++ )
    {
        t = 0, x = 0, y = 0, j = 0;
        fgets(linie,18,fin);
        
        while ( linie[j] != ' ' ) { x *= 10, x += (int)linie[j]-48, j++; }
        j++;
        while ( linie[j] >= '0' && linie[j] <= '9' ) { y *= 10, y += (int)linie[j]-48, j++; }
    
        
        memset(sel,0,sizeof(sel[0])*(k+1));
        for ( int i = x; i <= y; i++ )
            if ( !sel[a[i]] ) t += a[i]%modulo, sel[a[i]] = 1; 
        
        printf("%d\n", t%modulo);
    }
}