#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 131072
#define LOGMAX 18
#define PX 666013
#define MAX_DIM 10
int v[NMAX], poz[NMAX], vaux[NMAX], paux[NMAX], ci[NMAX * 2], cs[NMAX * 2], sum[NMAX * 2];
int ORSTdim[NMAX * 2], vx[NMAX >> 1], vy[NMAX >> 1], ve[NMAX >> 1];
int *ORSTx[NMAX * 2], **ORSTy[NMAX * 2], *ORSTci[NMAX * 2], *ORSTcs[NMAX * 2], **ORSTsum[NMAX * 2];
int i, j, k, l, N, M, P;
void msortvx(int li, int ls, int n)
{
int i, j, k, m;
if (li >= ls)
return;
m = (li + ls) >> 1;
msortvx(li, m, n);
msortvx(m + 1, ls, n);
i = k = li; j = m + 1;
while (i <= m && j <= ls)
{
if (vx[i] < vx[j])
{
ORSTx[n][k] = vx[i];
ORSTy[n][0][k] = vy[i];
ORSTsum[n][0][k] = ve[i];
k++;
i++;
}
else
{
ORSTx[n][k] = vx[j];
ORSTy[n][0][k] = vy[j];
ORSTsum[n][0][k] = ve[j];
k++;
j++;
}
}
if (i <= m)
{
for (j = i; j <= m; j++)
{
ORSTx[n][k] = vx[j];
ORSTy[n][0][k] = vy[j];
ORSTsum[n][0][k] = ve[j];
k++;
}
}
else // j <= ls
{
for (i = j; i <= ls; i++)
{
ORSTx[n][k] = vx[i];
ORSTy[n][0][k] = vy[i];
ORSTsum[n][0][k] = ve[i];
k++;
}
}
for (k = li; k <= ls; k++)
{
vx[k] = ORSTx[n][k];
vy[k] = ORSTy[n][0][k];
ve[k] = ORSTsum[n][0][k];
}
}
void msortORST(int li, int ls, int niv, int n1, int n)
{
int i, j, k, m;
if (li > ls)
return;
ORSTci[n][n1] = li;
ORSTcs[n][n1] = ls;
if (li >= ls)
{
ORSTy[n][niv][li] = vy[li];
ORSTsum[n][niv][li] = ve[li] % PX;
return;
}
m = (li + ls) >> 1;
msortORST(li, m, niv + 1, (n1 << 1), n);
msortORST(m + 1, ls, niv + 1, (n1 << 1) + 1, n);
i = li; j = m + 1; k = li;
while (i <= m && j <= ls)
{
if (vy[i] < vy[j])
{
ORSTy[n][0][k] = vy[i];
ORSTsum[n][0][k] = ve[i];
k++;
i++;
}
else
{
ORSTy[n][0][k] = vy[j];
ORSTsum[n][0][k] = ve[j];
k++;
j++;
}
}
if (i <= m)
{
for (j = i; j <= m; j++)
{
ORSTy[n][0][k] = vy[j];
ORSTsum[n][0][k] = ve[j];
k++;
}
}
else // j <= ls
{
for (i = j; i <= ls; i++)
{
ORSTy[n][0][k] = vy[i];
ORSTsum[n][0][k] = ve[i];
k++;
}
}
for (k = li; k <= ls; k++)
{
vy[k] = ORSTy[n][0][k];
ve[k] = ORSTsum[n][0][k];
}
ORSTy[n][niv][li] = vy[li];
ORSTsum[n][niv][li] = ve[li] % PX;
for (k = li + 1; k <= ls; k++)
{
ORSTy[n][niv][k] = vy[k];
ORSTsum[n][niv][k] = (ORSTsum[n][niv][k - 1] + ve[k]) % PX;
}
}
void buildORST(int n)
{
P = 1, l = 1;
while (P < ORSTdim[n])
P <<= 1, l++;
/*
for (i = ORSTdim[n] + 1; i <= P; i++)
vx[i] = N + i, vy[i] = ve[i] = 0;
ORSTdim[n] = P;
*/
ORSTx[n] = (int *) malloc((ORSTdim[n] + 1) * sizeof(int));
ORSTy[n] = (int**) malloc(l * sizeof(int*));
ORSTsum[n] = (int**) malloc(l * sizeof(int*));
for (i = 0; i < 1; i++)
{
ORSTy[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
ORSTsum[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
}
msortvx(1, ORSTdim[n], n);
for (i = 1; i <= ORSTdim[n]; i++)
ORSTx[n][i] = vx[i];
for (i = 1; i <= ORSTdim[n]; i++)
ORSTy[n][0][i] = vy[i],
ORSTsum[n][0][i] = ve[i];
if (ORSTdim[n] >= MAX_DIM)
{
for (i = 1; i < l; i++)
{
ORSTy[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
ORSTsum[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
}
ORSTci[n] = (int *) malloc(2 * (P + 1) * sizeof(int));
ORSTcs[n] = (int *) malloc(2 * (P + 1) * sizeof(int));
msortORST(1, ORSTdim[n], 0, 1, n);
}
else
ORSTci[n] = NULL;
}
inline int q2ORST(int li, int ls, int ymax, int n, int n1, int niv)
{
int cmid = (ORSTci[n][n1] + ORSTcs[n][n1]) >> 1;
int yp, yli, yls, ymid;
if (li == ORSTci[n][n1] && ls == ORSTcs[n][n1])
{
if (ymax < ORSTy[n][niv][ORSTci[n][n1]])
return 0;
yli = ORSTci[n][n1]; yls = ORSTcs[n][n1];
yp = 1;
while (yli <= yls)
{
ymid = (yli + yls) >> 1;
if (ORSTy[n][niv][ymid] <= ymax)
{
yp = ymid;
yli = ymid + 1;
}
else
yls = ymid - 1;
}
return ORSTsum[n][niv][yp];
}
if (ls <= cmid)
return q2ORST(li, ls, ymax, n, (n1 << 1), niv + 1);
if (li > cmid)
return q2ORST(li, ls, ymax, n, (n1 << 1) + 1, niv + 1);
return (q2ORST(li, cmid, ymax, n, (n1 << 1), niv + 1) + q2ORST(cmid + 1, ls, ymax, n, (n1 << 1) + 1, niv + 1)) % PX;
}
inline int qORST(int xmax, int ymax, int n)
{
int xp, li, ls, mid, rez;
if (ORSTdim[n] <= 0)
return 0;
if (ORSTci[n] == NULL)
{
rez = 0;
for (li = 1; li <= ORSTdim[n] && ORSTx[n][li] <= xmax; li++)
if (ORSTy[n][0][li] <= ymax)
rez = (rez + ORSTsum[n][0][li]) % PX;
return rez;
}
li = 1; ls = ORSTdim[n];
xp = 0;
while (li <= ls)
{
mid = (li + ls) >> 1;
if (ORSTx[n][mid] <= xmax)
{
xp = mid;
li = mid + 1;
}
else
ls = mid - 1;
}
if (xp > 0)
return q2ORST(1, xp, ymax, n, 1, 0);
return 0;
}
void mergesort(int li, int ls, int n)
{
int m;
if (li > ls || n > (2 * NMAX - 1))
return;
ci[n] = li;
cs[n] = ls;
ORSTdim[n] = 0;
if (li >= ls)
{
sum[n] = v[li] % PX;
return;
}
m = (li + ls) >> 1;
mergesort(li, m, n << 1);
mergesort(m + 1, ls, (n << 1) + 1);
// compute position intervals
i = li; j = m + 1;
while (i <= m && j <= ls)
{
while (i < m && v[i] == v[i + 1])
i++;
if (v[i] == v[j])
{
// we have common position interval [ poz[i], poz[j] ]
//fprintf(stderr, "n=%d,v=%d,p1=%d,x=%d,cmid=%d,p2=%d\n", n, v[i], poz[i], m - poz[i] + 1, m, poz[j]);
ORSTdim[n]++;
vx[ORSTdim[n]] = m - poz[i] + 1;
vy[ORSTdim[n]] = poz[j];
ve[ORSTdim[n]] = v[i];
//ve.push_back(make_pair(v[i], make_pair(cmid[n] - poz[i] + 1, poz[j])));
while (j < ls && v[j] == v[j + 1])
j++;
j++;
}
else
if (v[i] < v[j])
i++;
else
{
while (j < ls && v[j] == v[j + 1])
j++;
j++;
}
}
// build an orthogonal range search tree for the common pairs
if (ORSTdim[n] > 0)
buildORST(n);
// merge
i = li; j = m + 1; k = li;
while (i <= m && j <= ls)
{
if (v[i] <= v[j])
{
vaux[k] = v[i];
paux[k] = poz[i];
k++;
i++;
}
else
{
vaux[k] = v[j];
paux[k] = poz[j];
k++;
j++;
}
}
if (i <= m)
{
for (j = i; j <= m; j++)
{
vaux[k] = v[j];
paux[k] = poz[j];
k++;
}
}
else // j <= ls
{
for (i = j; i <= ls; i++)
{
vaux[k] = v[i];
paux[k] = poz[i];
k++;
}
}
for (k = li; k <= ls; k++)
v[k] = vaux[k],
poz[k] = paux[k];
sum[n] = v[li] % PX;
for (k = li + 1; k <= ls; k++)
if (v[k] > v[k - 1])
sum[n] = (sum[n] + v[k]) % PX;
}
inline int query(int li, int ls, int n)
{
int cmid = (ci[n] + cs[n]) >> 1;
if (li == ci[n] && ls == cs[n])
return sum[n];
if (ls <= cmid)
return query(li, ls, (n << 1));
if (li > cmid)
return query(li, ls, (n << 1) + 1);
return (query(li, cmid, (n << 1)) + query(cmid + 1, ls, (n << 1) + 1) - qORST(cmid - li + 1, ls, n) + PX) % PX;
}
int main()
{
freopen("distincte.in", "r", stdin);
scanf("%d %d %d", &N, &k, &M);
for (i = 1; i <= N; i++)
scanf("%d", &v[i]);
/*
P = 1;
while (P < N)
P <<= 1;
for (i = N + 1; i <= P; i++)
v[i] = 0;
N = P;
*/
//fprintf(stderr, "%d\n", P);
for (i = 1; i <= N; i++)
poz[i] = i;
mergesort(1, N, 1);
freopen("distincte.out", "w",stdout);
while (M--)
{
scanf("%d %d", &i, &j);
printf("%d\n", query(i, j, 1));
}
return 0;
}