#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 131072
#define LOGMAX 18
#define PX 666013
#define MAX_DIM 0
struct ORSTinfo {
int ORSTdim;
int *ORSTci, *ORSTcs;
int *ORSTx, **ORSTy, **ORSTsum;
int **ORSTpoz, **ORSTlastdif;
char **ORSTson;
} *orsti[2 * NMAX];
int v[NMAX], poz[NMAX], vaux[NMAX], paux[NMAX], ci[NMAX * 2], cs[NMAX * 2], sum[NMAX * 2];
int vx[NMAX >> 1], vy[NMAX >> 1], ve[NMAX >> 1], ldif[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])
{
orsti[n]->ORSTx[k] = vx[i];
orsti[n]->ORSTy[0][k] = vy[i];
orsti[n]->ORSTsum[0][k] = ve[i];
k++;
i++;
}
else
{
orsti[n]->ORSTx[k] = vx[j];
orsti[n]->ORSTy[0][k] = vy[j];
orsti[n]->ORSTsum[0][k] = ve[j];
k++;
j++;
}
}
if (i <= m)
{
for (j = i; j <= m; j++)
{
orsti[n]->ORSTx[k] = vx[j];
orsti[n]->ORSTy[0][k] = vy[j];
orsti[n]->ORSTsum[0][k] = ve[j];
k++;
}
}
else // j <= ls
{
for (i = j; i <= ls; i++)
{
orsti[n]->ORSTx[k] = vx[i];
orsti[n]->ORSTy[0][k] = vy[i];
orsti[n]->ORSTsum[0][k] = ve[i];
k++;
}
}
for (k = li; k <= ls; k++)
{
vx[k] = orsti[n]->ORSTx[k];
vy[k] = orsti[n]->ORSTy[0][k];
ve[k] = orsti[n]->ORSTsum[0][k];
}
}
void msortORST(int li, int ls, int niv, int n1, int n)
{
int i, j, k, m;
if (li > ls)
return;
orsti[n]->ORSTci[n1] = li;
orsti[n]->ORSTcs[n1] = ls;
if (li >= ls)
{
orsti[n]->ORSTy[niv][li] = vy[li];
orsti[n]->ORSTsum[niv][li] = ve[li] % PX;
orsti[n]->ORSTpoz[niv][li] = 0;
orsti[n]->ORSTlastdif[niv][li] = 0;
orsti[n]->ORSTson[niv][li] = 0;
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])
{
orsti[n]->ORSTy[0][k] = vy[i];
orsti[n]->ORSTsum[0][k] = ve[i];
orsti[n]->ORSTpoz[niv][k] = i;
orsti[n]->ORSTson[niv][k] = 0;
k++;
i++;
}
else
{
orsti[n]->ORSTy[0][k] = vy[j];
orsti[n]->ORSTsum[0][k] = ve[j];
orsti[n]->ORSTpoz[niv][k] = j;
orsti[n]->ORSTson[niv][k] = 1;
k++;
j++;
}
}
if (i <= m)
{
for (j = i; j <= m; j++)
{
orsti[n]->ORSTy[0][k] = vy[j];
orsti[n]->ORSTsum[0][k] = ve[j];
orsti[n]->ORSTpoz[niv][k] = j;
orsti[n]->ORSTson[niv][k] = 0;
k++;
}
}
else // j <= ls
{
for (i = j; i <= ls; i++)
{
orsti[n]->ORSTy[0][k] = vy[i];
orsti[n]->ORSTsum[0][k] = ve[i];
orsti[n]->ORSTpoz[niv][k] = i;
orsti[n]->ORSTson[niv][k] = 1;
k++;
}
}
ldif[0] = ldif[1] = 0;
for (k = li; k <= ls; k++)
{
vy[k] = orsti[n]->ORSTy[0][k];
ve[k] = orsti[n]->ORSTsum[0][k];
orsti[n]->ORSTlastdif[niv][k] = ldif[1 - orsti[n]->ORSTson[niv][k]];
ldif[orsti[n]->ORSTson[niv][k]] = orsti[n]->ORSTpoz[niv][k];
}
orsti[n]->ORSTy[niv][li] = vy[li];
orsti[n]->ORSTsum[niv][li] = ve[li] % PX;
for (k = li + 1; k <= ls; k++)
{
orsti[n]->ORSTy[niv][k] = vy[k];
orsti[n]->ORSTsum[niv][k] = (orsti[n]->ORSTsum[niv][k - 1] + ve[k]) % PX;
}
}
void buildORST(int n, int dim)
{
orsti[n] = (struct ORSTinfo*) malloc(sizeof(struct ORSTinfo));
orsti[n]->ORSTdim = dim;
P = 1, l = 1;
while (P < orsti[n]->ORSTdim)
P <<= 1, l++;
/*
for (i = ORSTdim[n] + 1; i <= P; i++)
vx[i] = N + i, vy[i] = ve[i] = 0;
ORSTdim[n] = P;
*/
orsti[n]->ORSTx = (int *) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
orsti[n]->ORSTy = (int**) malloc(l * sizeof(int*));
orsti[n]->ORSTsum = (int**) malloc(l * sizeof(int*));
for (i = 0; i < 1; i++)
{
orsti[n]->ORSTy[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
orsti[n]->ORSTsum[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
}
msortvx(1, orsti[n]->ORSTdim, n);
for (i = 1; i <= orsti[n]->ORSTdim; i++)
orsti[n]->ORSTx[i] = vx[i];
for (i = 1; i <= orsti[n]->ORSTdim; i++)
orsti[n]->ORSTy[0][i] = vy[i],
orsti[n]->ORSTsum[0][i] = ve[i];
if (orsti[n]->ORSTdim >= MAX_DIM)
{
for (i = 1; i < l; i++)
{
orsti[n]->ORSTy[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
orsti[n]->ORSTsum[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
}
orsti[n]->ORSTpoz = (int**) malloc(l * sizeof(int*));
orsti[n]->ORSTlastdif = (int**) malloc(l * sizeof(int*));
orsti[n]->ORSTson = (char**) malloc(l * sizeof(char*));
for (i = 0; i < l; i++)
{
orsti[n]->ORSTpoz[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
orsti[n]->ORSTlastdif[i] = (int*) malloc((orsti[n]->ORSTdim + 1) * sizeof(int));
orsti[n]->ORSTson[i] = (char*) malloc((orsti[n]->ORSTdim + 1) * sizeof(char));
}
orsti[n]->ORSTci = (int *) malloc(2 * (P + 1) * sizeof(int));
orsti[n]->ORSTcs = (int *) malloc(2 * (P + 1) * sizeof(int));
msortORST(1, orsti[n]->ORSTdim, 0, 1, n);
}
else
orsti[n]->ORSTci = NULL;
}
inline int q2ORST(int li, int ls, int ymax, int n, int n1, int niv)
{
int cmid = (orsti[n]->ORSTci[n1] + orsti[n]->ORSTcs[n1]) >> 1;
int yp, yli, yls, ymid;
if (li == orsti[n]->ORSTci[n1] && ls == orsti[n]->ORSTcs[n1])
{
if (ymax < orsti[n]->ORSTy[niv][orsti[n]->ORSTci[n1]])
return 0;
yli = orsti[n]->ORSTci[n1]; yls = orsti[n]->ORSTcs[n1];
yp = 1;
while (yli <= yls)
{
ymid = (yli + yls) >> 1;
if (orsti[n]->ORSTy[niv][ymid] <= ymax)
{
yp = ymid;
yli = ymid + 1;
}
else
yls = ymid - 1;
}
return orsti[n]->ORSTsum[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 (orsti[n] == NULL)
return 0;
if (orsti[n]->ORSTci == NULL)
{
rez = 0;
for (li = 1; li <= orsti[n]->ORSTdim && orsti[n]->ORSTx[li] <= xmax; li++)
if (orsti[n]->ORSTy[0][li] <= ymax)
rez = (rez + orsti[n]->ORSTsum[0][li]) % PX;
return rez;
}
li = 1; ls = orsti[n]->ORSTdim;
xp = 0;
while (li <= ls)
{
mid = (li + ls) >> 1;
if (orsti[n]->ORSTx[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, dim;
if (li > ls || n > (2 * NMAX - 1))
return;
ci[n] = li;
cs[n] = ls;
dim = 0;
orsti[n] = NULL;
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]);
dim++;
vx[dim] = m - poz[i] + 1;
vy[dim] = poz[j];
ve[dim] = 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 (dim > 0)
buildORST(n, dim);
// 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;
}