#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 100100
#define MOD 666013

typedef struct t_query { int start, end, ind; } t_query;

int N, M, K, A[MAXN], poz[MAXN], aib[MAXN], sum[MAXN], ans[MAXN];
t_query Q[MAXN];

int cmp(t_query a, t_query b)
{
    return a.end < b.end;
}

void update(int x, int val)
{
    for(; x <= N; x += (x^(x-1))&x)
    {
        aib[x] += val;
        if(aib[x] >= MOD)
            aib[x] -= MOD;
    }
}

int query(int x)
{
    int val = 0;
    for(; x > 0; x -= (x^(x-1))&x)
    {
        val += aib[x];
        if(val >= MOD)
            val -= MOD;
    }
    return val;
}

void solve(void)
{
    int i, x, p = 1, s, f, r;

    for(i = 1; i <= N; i++)
    {
        sum[i] = A[i]+sum[i-1];
        if(sum[i] >= MOD)
            sum[i] -= MOD;
    }

    sort(Q+1, Q+M+1, cmp);

    for(i = 1; i <= N; i++)
    {
        x = A[i];

        if(!poz[x])
            poz[x] = i;
        else
            update(N-poz[x]+1, x), poz[x] = i;

        while(p <= N && Q[p].end == i)
        {
            s = Q[p].start;
            r = sum[i]-sum[s-1]+MOD;
            while(r >= MOD)
                r -= MOD;
            r = r - query(N-s+1) + MOD;
            while(r >= MOD)
                r -= MOD;
            ans[Q[p].ind] = r;
            p++;
        }
    }
}

void read_data(void)
{
    int i, j, k;

    scanf("%d %d %d\n", &N, &K, &M);

    for(i = 1; i <= N; i++)
        scanf("%d\n", &A[i]);

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d\n", &j, &k);
        Q[i].start = j, Q[i].end = k, Q[i].ind = i;
    }
}

void write_data(void)
{
    int i;

    for(i = 1; i <= M; i++)
        printf("%d\n", ans[i]);
}

int main(void)
{
    freopen("distincte.in", "rt", stdin);
    freopen("distincte.out", "wt", stdout);
    
    read_data();
    solve();
    write_data();

    return 0;
}