#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
#endif

const int MOD = 666013;

struct Query {
    int st, dr, idx;
} qr[100002];

int n, k, q, i, a[100002];
int fr[100002], bks;
long long sum, rasp[100002];

static inline bool Cmp(Query a, Query b) {
    if(a.st / bks != b.st / bks) return a.st / bks < b.st / bks;
    if(0 == (a.st / bks) % 2) return a.dr < b.dr;
                              return a.dr > b.dr;
}

static inline void Add(int poz) {
    fr[a[poz]]++;
    if(1 == fr[a[poz]]) sum = (sum + a[poz]) % MOD;
}

static inline void Del(int poz) {
    fr[a[poz]]--;
    if(0 == fr[a[poz]]) sum = ((sum - a[poz]) % MOD + MOD) % MOD;
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    
    fin >> n >> k >> q;
    for(i = 1; i <= n; i++) {
        fin >> a[i];
    }
    
    for(i = 1; i <= q; i++) {
        fin >> qr[i].st >> qr[i].dr;
        qr[i].idx = i;
    }
    
    bks = sqrt(n);
    
    sort(qr + 1, qr + q + 1, Cmp);
    
    int st = 1, dr = 0;
    for(i = 1; i <= q; i++) {
        while(qr[i].st < st) Add(--st);
        while(dr < qr[i].dr) Add(++dr);
        
        while(st < qr[i].st) Del(st++);
        while(qr[i].dr < dr) Del(dr--);
        
        rasp[qr[i].idx] = sum;
    }
    for(i = 1; i <= q; i++) fout << rasp[i] << "\n";

    return 0;
}