# include <cstdio>
# define MAX 100010
# include <algorithm>
# define ub(x) (x&(-x))
# define MOD 666013

using namespace std;

struct da{int x,y,z;};
da op[MAX];

struct da1{int x,y;};
da1 sol[MAX];

int n,m,k;
int aib[MAX], ok[MAX], a[MAX];

int cmp1(da1 A, da1 B) {
    if (A.y > B.y) return true;
    if (A.y== B.y) if (A.x > B.x) return true;
    return false;
}
int cmp(da A, da B) {
    if (A.y > B.y) return true;
    if (A.y == B.y) if (A.x > B.x) return true;
    return false;
}

void update(int poz, int val) {
    int i;
    for (i = poz; i <= n; i += ub(i))
        aib[i] = (aib[i] + val + MOD) % MOD;
}

int calc (int poz) {
    int s = 0,i;
    for (i = poz; i ; i -= ub(i))
        s = (s + aib[i]) % MOD;
    return s;
}
int main ()
{

    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    scanf("%d %d %d", &n, &k, &m);
    int i,j;
    for (i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    for (i = 1; i <= m; i++) {
        scanf("%d %d",&op[i].x, &op[i].y);
        op[i].z = i;
    }
    sort (op + 1, op + m + 1, cmp);

    for (j=1 , i = 1; i <= m; i++){
    for (; j <= op[i].y; j++) {
            if ( ok[a[j]] )  update(ok[a[j]], -a[j]);
            update (j, a[j]);
            ok[a[j]] = j;
    }
    sol[i].x = op[i].z;
    sol[i].y = (calc(op[i].y) - calc(op[i].x-1) + MOD) % MOD;
    }

    sort (sol + 1, sol + m + 1, cmp1);

    for (i = 1; i <= m; i++)
        printf("%d\n",sol[i].y);


    return 0;
}