#include <stdio.h>
#include <algorithm>
using namespace std;
#define nm 100100
#define mm 350100
#define mod 666013
struct interv
{
int x, y;
};
int n, k, m, a[nm], c[mm], p[nm], sol[nm], used[nm], tmp;
interv v[nm];
int cmp(int a, int b)
{
return v[a].y < v[b].y;
}
void add(int pos, int val)
{
used[val] = pos - tmp + 1;
while(pos)
{
c[pos] += val;
if (c[pos] >= mod)
c[pos] -= mod;
if (c[pos] < 0)
c[pos] += mod;
pos >>= 1;
}
}
int querry(int nod, int st, int dr, int x, int y)
{
if (st == x && dr == y)
return c[nod];
if (dr <= (x + y) / 2)
return querry(nod * 2, st, dr, x, (x + y) / 2);
if (st > (x + y) / 2)
return querry(nod * 2 + 1, st, dr, (x + y) / 2 + 1, y);
return (querry(nod * 2, st, (x + y) / 2, x, (x + y) / 2) + querry(nod * 2 + 1, (x + y) / 2 + 1, dr, (x + y) / 2 + 1, y)) % mod;
}
int main()
{
int i, j;
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", &a[i]);
for (i = 1; i <= m; ++i)
{
scanf("%d%d", &v[i].x, &v[i].y);
p[i] = i;
}
sort(p + 1, p + m + 1, cmp);
for (tmp = 1; tmp < n; tmp <<= 1);
for (i = 1, j = 1; i <= m; ++i)
{
for (; j <= v[p[i]].y; ++j)
{
if (used[a[j]])
add(tmp - 1 + used[a[j]], -a[j]);
add(tmp - 1 + j, a[j]);
}
sol[p[i]] = querry(1, v[p[i]].x, v[p[i]].y, 1, tmp);
}
for (i = 1; i <= m; ++i)
printf("%d\n", sol[i]);
}