#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;


#define nmax 100010
#define modulo 666013


int Last[nmax], N, M, K, A[nmax];
struct data
{
       int x, y, ind;
}V[nmax];
long long AIB[nmax], ans[nmax];

bool cmp(data one, data two) 
{
     return one.y < two.y;
}


void Update(int pos, int val)
{
     if(pos == 0) return ;
     for(; pos <= N; pos += (pos & (-pos)))
           AIB[pos] += val;
}

long long Query(int pos)
{
     long long sum = 0;
     for(; pos; pos -= (pos & (-pos)))
           sum += AIB[pos];
     return sum;
}


int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    int i, j;
    scanf("%i %i %i", &N, &K, &M);
    for(i = 1; i <= N; i++)
          scanf("%i", &A[i]);
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i", &V[i].x, &V[i].y);
          V[i].ind = i;
    }
    sort(V + 1, V + M + 1, cmp); 
    for(i = 1, j = 1; i <= M; i++)
    {
          while(j <= V[i].y)
          {
                  Update(Last[A[j]], -A[j]);
                  Update(j, A[j]);
                  Last[A[j]] = j;
                  j ++;
          }
          ans[V[i].ind] = Query(V[i].y) - Query(V[i].x - 1);
    }
    for(i = 1; i <= M; i++)
          printf("%lld\n", ans[i] % modulo);
    return 0;
}