#include <cstdio>
#include <algorithm>

using namespace std;

const int nmax = 100000;
const int mod = 666013;

int a[nmax+5];
int last[nmax+5];
int aib[nmax+5];
int answers[nmax+5];

struct query_keeper
{
    int a, b, nr, answer;
};

query_keeper q[nmax+5];
int n, k, m;

inline int lsb(int x)
{
    return x&-x;
}

void update(int pos, int val)
{
    for(int i=pos; i<=n; i+=lsb(i))
    {
        aib[i] += val;
        aib[i] %= mod;
    }
}

int query(int pos)
{
    int ans = 0;
    for(int i=pos; i>0; i-=lsb(i))
    {
        ans+= aib[i];
        ans %= mod;
    }
    return ans;
}

bool cmp(query_keeper a, query_keeper b)
{
    return a.a < b.a || (a.a == b.a && a.b<b.b);
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    scanf("%d%d%d", &n, &k, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=0; i<m; i++)
    {
        int st, dr;
        scanf("%d%d", &st, &dr);
        q[i].a = st;
        q[i].b = dr;
        q[i].nr = i;
    }
    sort(q, q+m, cmp);
    int pos = 1;
    for(int i=0; i<m; i++)
    {
        while(pos <= q[i].b)
        {
            if(last[a[pos]])update(last[a[pos]], -a[pos]);
            update(pos, a[pos]);
            last[a[pos]] = pos;
            pos++;
        }
        q[i].answer = (query(q[i].b) - query(q[i].a - 1) + mod) %mod;
    }
    for(int i=0; i<m; i++)
        answers[q[i].nr] = q[i].answer;
    for(int i=0; i<m; i++)
        printf("%d\n", answers[i]);
    return 0;
}