#include <stdio.h>
#include <algorithm>
#define aduna(x, y) (((x+=y) >= MOD) ? (x -= MOD) : 0)
#define MOD 666013
#define NMax 100005

using namespace std;

typedef struct { int x, y, ord; } entry;

int N, K, v[NMax], prev[NMax], O[NMax], Res[NMax], A[NMax], S[NMax];
entry Q[NMax];

bool operator< (const entry &a, const entry& b)
{ return a.y < b.y; }

void update(int X, int val)
{    
     for (; X <= N; X += X^(X-1) & X)
         aduna(A[X], val);         
}

int query(int X)
{
    int S;
    
    for (S = 0; X; X -= X^(X-1) & X)
        aduna(S, A[X]);
    return S;
}

int main(void)
{
    int M, i, j, cnt = 0;
    
    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]);
        S[i] = S[i-1];
        aduna(S[i], v[i]);
    }
    
    for (i = 1; i <= K; i++) O[i] = 0;
    
    for (i = 1; i <= N; i++)
    {
        prev[i] = N - O[v[i]];
        O[v[i]] = i;
    }
        
    for (i = 1; i <= M; i++)
    {
        scanf("%d %d", &Q[i].x, &Q[i].y);
        Q[i].ord = i; 
    }
    sort(Q+1, Q+M+1);
        
    j = 1;
    for (i = 1; i <= N; i++)
    {
        update(prev[i], v[i]);
        
        for (; j <= M && Q[j].y == i; j++)
        {
            cnt = S[i] - S[Q[j].x-1];
            if (cnt < 0) cnt += MOD;
            cnt -= query(N-Q[j].x);
            if (cnt < 0) cnt += MOD;            
            
            Res[Q[j].ord] = cnt;
        }
        
    }
       
    for (i = 1; i <= M; i++)
        printf("%d\n", Res[i]);
    
    return 0;
}