#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100002
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second
#define modulo 666013
int lst[NMAX];
int ARB[3*NMAX];
int A[NMAX];
int ans[NMAX];
vector< pair< pair<int, int>, int> > V;
int N, M, K;
void update(int nod, int st, int dr, int val, int poz)
{
if (st == dr) ARB[nod] = val % modulo;
else
{
int mid = (st + dr) / 2;
if (poz <= mid) update(nod*2, st, mid, val, poz);
else update(nod*2+1, mid+1, dr, val, poz);
ARB[nod] = (ARB[nod*2] + ARB[nod*2+1]) % modulo;
}
}
int query(int nod, int st, int dr, int a, int b)
{
if (a <= st && dr <= b) return ARB[nod];
else
{
int mid = (st + dr) / 2;
int ans = 0;
if (a <= mid) ans += query(nod*2, st, mid, a, b);
if (b > mid) ans += query(nod*2+1, mid+1, dr, a, b);
return ans % modulo;
}
}
int main()
{
freopen("distincte.in","r",stdin);
freopen("distincte.out","w",stdout);
int i, j, x, y, mx=0;
scanf("%d %d %d", &N, &K, &M);
for (i = 1; i <= N; i++)
scanf("%d ", &A[i]);
for (i = 1; i <= M; i++)
{
scanf("%d %d", &x, &y);
V.pb( mp(mp(y, x), i) );
}
sort(V.begin(), V.end());
for (i = 0; i < M; i++)
{
x = V[i].ff.ss; y = V[i].ff.ff;
for (j = mx + 1; j <= y; j++)
{
if (lst[ A[j] ]) update(1, 1, N, 0, lst[ A[j] ]);
lst[ A[j] ] = j;
update(1, 1, N, A[j], j);
}
mx = y;
ans[ V[i].ss ] = query(1, 1, N, x, y);
}
for (i = 1; i <= M; i++)
printf("%d\n", ans[i]);
return 0;
}