#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3F3F3F3F

typedef long long LL;

#define NMAX 100005
int N, K, M, a[NMAX], p[NMAX], lst[NMAX];
LL t[NMAX], Ans[NMAX];

pair<pair<int, int>, int> Q[NMAX];
pair<int, int> e[NMAX];

#define LSB(x) ((x) ^ ((x) & ((x)-1)))

void add(int x, int d)
{
	for (; x < NMAX; x += LSB(x))
		t[x] += d;
}

LL query(int x)
{
	LL r = 0;
	for (; x > 0; x -= LSB(x))
		r += t[x];
	return r;
}

LL dAns[NMAX];
vector<int> dumb;
LL bq(int x, int y)
{
    dumb.clear();
    FOR(i, x, y)
        dumb.PB(a[i]);

    sort(ALL(dumb));
    dumb.resize(unique(ALL(dumb)) - dumb.begin());

//    printf("=============\n");
//    FORI(it, dumb) printf("%d ", *it); printf("\n");
//    printf("=============\n");

    LL ret = 0;
    FORI(it, dumb)
        ret += (LL)*it;
    return ret;
}

void gen(void)
{
    freopen("distincte.in", "w", stdout);
    N = 20, M = 100;
    printf("%d %d %d\n", N, N, M);
    REP(i, N) printf("%d\n", 1+rand() % 20);
    REP(i, M)
    {
        int x, y;
        x = 1+(rand() % N), y = 1+(rand() % N);
        if (x > y) swap(x, y);
        printf("%d %d\n", x, y);
    }
}

int main(void)
{
//gen(); return 0;
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
	scanf("%d %d %d", &N, &K, &M);

	CLEAR(lst);
	FOR(i, 1, N) 
	{
		scanf("%d", &a[i]);
		p[i] = lst[a[i]], lst[a[i]] = i, e[i] = MP(p[i], i);
	}

	int x, y;
	REP(i, M)
    {
        scanf("%d %d", &x, &y), Q[i] = MP(MP(x, y), i);
//        dAns[i] = bq(x, y);
    }

	CLEAR(t);

	sort(e+1, e+N+1), sort(Q, Q+M);

	int pt = 1;
	REP(i, M)
	{
		for (; pt <= N && e[pt].first < Q[i].first.first; pt ++)
			add(e[pt].second, a[e[pt].second]);
		Ans[Q[i].second] = query(Q[i].first.second) - query(Q[i].first.first - 1);
	}

	REP(i, M)
    {
        printf("%lld\n", Ans[i] % 666013);
//        if (Ans[i] != dAns[i])
//        {
//            printf("%d wtf!!!\n", i);
//            return 0;
//        }
    }

    return 0;
}