#include <bits/stdc++.h>
#define int long long

FILE *in = fopen("distincte.in", "r"), *out = fopen("distincte.out", "w") ;

const int MV = 1e5 ;
const int MOD = 666013 ;

int n, k, m ;

typedef std::pair<int, int> PII ;

std::vector<PII> offline[MV + 5] ; /// rezolvam querry-urile offline dupa capat dreapta
int v[MV + 5] ;
int prev[MV + 5] ;
int aib[MV + 5] ;
int ans[MV + 5] ;

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

int querry(int poz) {
        int ret(0) ;
        for (int i = poz ; i > 0 ; i -= (i & -i)) {
                ret += aib[i] ;
        }
        return ret ;
}

signed main() {
        fscanf(in, "%lld %lld %lld", &n, &k, &m) ;
        for (int i = 1 ; i <= n ; ++ i) {
                fscanf(in, "%lld", v + i) ;
        }
        int left, right ;
        for (int i = 1 ; i <= m ; ++ i) {
                fscanf(in, "%lld %lld", &left, &right) ;
                offline[right].push_back({left, i}) ; /// binecuvantat fie chiriac ca mi-a zis ca pot sa fac offline
        }
        for (int i = 1 ; i <= n ; ++ i) {
                if (prev[v[i]] != 0) {
                        /// update(prev[v[i]], -1) ;  :((((((   ne cere suma nu cate sunt :((
                        update(prev[v[i]], -v[i]) ;
                }
                prev[v[i]] = i ;
                /// update(i, 1) ; la fel
                update(i, v[i]) ;
                std::sort(begin(offline[i]), end(offline[i])) ;
                for (auto it : offline[i]) {
                        ans[it.second] = (querry(i) - querry(it.first - 1)) % MOD ;
                }
        }
        for (int i = 1 ; i <= m ; ++ i) {
                fprintf(out, "%lld\n", ans[i]) ;
        }
}