#include <algorithm>
#include <stdio.h>
#include <utility>
#define MAX 100001
#define MOD 666013

std::pair<int, int> q[ MAX + 10 ];

bool cmp( int a, int b ) {
  return q[ a ].second < q[ b ].second;
}

int a[ MAX + 10 ];
int poz[ MAX + 10 ];
int last[ MAX + 10 ];

long long aib[ MAX + 10 ];
long long rez[ MAX + 10 ];

int n, m, x, k;

void update( int x, int y ) {
  if( x == 0 )
    return;
  for( ; x <= n; x += x & ( -x ) )
    aib[ x ] += y;
}

long long query( int x ) {
  long long s = 0;
  for( ; x; x -= x & ( -x ) )
    s += aib[ x ];
  return s;
}

int main()
{
    FILE *fin = fopen( "distincte.in",  "r" );
    fscanf( fin, "%d%d%d", &n, &k, &m );
    for( int i = 1; i <= n; i++ )
      fscanf( fin, "%d", &a[ i ] );
    for( int i = 1; i <= m; i++ ) {
      fscanf( fin, "%d%d", &q[ i ].first, &q[ i ].second );
      poz[ i ] = i;
    }
    fclose( fin );

    std::sort( poz + 1, poz + m + 1, cmp );

    int j = 1;
    for( int i = 1; i <= m; i++ ) {
      while( j <= q[ poz[ i ] ].second ) {
        update( last[ a[ j ] ], -a[ j ] );
        update( j, a[ j ] );
        last[ a[ j ] ] = j; ++j;
      }
      rez[ poz[ i ] ] = query( q[ poz[ i ] ].second ) - query( q[ poz[ i ] ].first - 1 );
    }

    FILE *fout = fopen( "distincte.out", "w" );
    for( int i = 1; i <= m; i++ )
      fprintf( fout, "%lld\n", rez[ i ] % MOD );
    fclose( fout );
    return 0;
}