#include <iostream>
#include <algorithm>
#define NMAX 100
#define MOD 666013
using namespace std;
struct interval
{
int pos;
int val;
int next;
};
struct Query
{
int st;
int dr;
int pos;
};
int N, K, M, last[NMAX], T[4*NMAX], v_pos = 1, pos, S, E, val = 0;
int O[NMAX];
interval v[NMAX];
Query Q[NMAX];
void build(int node, int st, int dr)
{
if(st == dr)
{
T[node] = v[st].val;
}
else
{
int mid = (st + dr) / 2;
build(2 * node, st, mid);
build(2 * node + 1, mid + 1, dr);
T[node] = (T[2 * node] + T[2 * node + 1]) % MOD;
}
}
void update(int node, int st, int dr)
{
if(st == dr)
{
T[node] = 0;
}
else
{
int mid = (st + dr) / 2;
if(pos <= mid)
{
update(2 * node, st, mid);
}
else
{
update(2 * node + 1, mid + 1, dr);
}
T[node] = (T[2 * node] + T[2 * node + 1]) % MOD;
}
}
void query(int node, int st, int dr)
{
if(S <= st && dr <= E)
{
val += T[node];
}
else
{
int mid = (st + dr) / 2;
if(S <= mid)
{
query(2 * node, st, mid);
}
if(E > mid)
{
query(2 * node + 1, mid + 1, dr);
}
}
}
bool cmp_interval(interval A, interval B) {
return A.next < B.next;
}
bool cmp_query(Query A, Query B) {
return A.dr < B.dr;
}
int main()
{
freopen("distincte.in", "r", stdin);
freopen("distincte.out", "w", stdout);
scanf("%d %d %d", &N, &K, &M);
for(int i = 1; i <= N; i++)
{
scanf("%d", &v[i].val);
v[i].next = N + 1;
v[i].pos = i;
v[last[v[i].val]].next = i;
last[v[i].val] = i;
}
build(1, 1, N);
for(int i = 1; i <= M; i++)
{
scanf("%d %d", &Q[i].st, &Q[i].dr);
Q[i].pos = i;
}
sort(v + 1, v + N + 1, cmp_interval);
sort(Q + 1, Q + M + 1, cmp_query);
for(int i = 1; i <= M; i++)
{
while(v_pos <= N && v[v_pos].next <= Q[i].dr)
{
pos = v[v_pos].pos;
update(1, 1, N);
v_pos++;
}
S = Q[i].st;
E = Q[i].dr;
val = 0;
query(1, 1, N);
O[Q[i].pos] = val;
}
for(int i = 1; i <= M; i++) {
printf("%d\n", O[i]);
}
return 0;
}