#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

#define BUF_SIZE 4096
char buf[BUF_SIZE];
int pos = BUF_SIZE;

inline char getChar(FILE *f) {
  if (pos == BUF_SIZE) {
    fread(buf, 1, BUF_SIZE, f);
    pos = 0;
  }
  return buf[pos++];
}

inline int read(FILE *f) {
  int result = 0;
  char c;
  do {
    c = getChar(f);
  } while (!isdigit(c));

  do {
    result = 10 * result + c - '0';
    c = getChar(f);
  } while (isdigit(c));

  return result;
}

struct QUERY
{
    int x, y;
    int ind;

    bool operator < ( const QUERY &q ) const
    {
        return y < q.y;
    }
};

const int Nmax = 100000;
const int Qmax = 200000;
const int Vmax = 100000;

int v[Nmax + 1];
int AIB[Nmax + 1];
QUERY queries[Qmax + 1];
int solution[Qmax + 1];
int vis[Vmax + 1];

int N, Q, K;

inline int lsb( int x )
{
    return x & ( -x );
}

void update( int x, int val )
{
    for ( int i = x; i <= N; i += lsb( i ) )
            AIB[i] = ( AIB[i] + val ) % 666013;
}

int query( int x )
{
    int s = 0;

    for ( int i = x; i >= 1; i -= lsb( i ) )
            s = ( s + AIB[i] ) % 666013;

    return s;
}

int main()
{
    FILE *f = fopen( "distincte.in", "r" );
    FILE *g = fopen( "distincte.out", "w" );

    N = read( f );
    K = read( f );
    Q = read( f );

    for ( int i = 1; i <= N; ++i )
            v[i] = read( f );

    for ( int i = 1; i <= Q; ++i )
    {
        queries[i].x = read( f );
        queries[i].y = read( f );
        queries[i].ind = i;
    }

    sort( queries + 1, queries + Q + 1 );

    for ( int i = 1; i <= Q; ++i )
    {
        for ( int j = queries[i - 1].y + 1; j <= queries[i].y; ++j )
        {
            if ( vis[ v[j] ] )
                    update( vis[ v[j] ], -v[j] );

            vis[ v[j] ] = j;
            update( vis[ v[j] ], v[j] );
        }

        solution[ queries[i].ind ] = query( queries[i].y ) - query( queries[i].x - 1 );
    }

    for ( int i = 1; i <= Q; ++i )
            fprintf(g, "%d\n", solution[i]);

    return 0;
}