#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;

const int NMAX = 100'000;
const int MOD = 666'013;
int B;

int a[NMAX];
int f[NMAX];
int ans[NMAX];
int sum = 0;

struct str {int l, r, p;} b[NMAX];

void add(int x) {
    if(!f[a[x]])
        sum += a[x];
    if(sum >= MOD)
        sum -= MOD;
    f[a[x]] ++;
}

void rem(int x) {
    f[a[x]] --;
    if(!f[a[x]])
        sum -= a[x];
    if(sum < 0)
        sum += MOD;
}

signed main() {
    ifstream cin("distincte.in");
    ofstream cout("distincte.out");
    
    int n, k, q; cin >> n >> k >> q;
    B = sqrt(n);
    for(int i = 0; i < n; cin >> a[i ++]);

    for(int i = 0; i < q; i ++) {
        auto &[l, r, p] = b[i];
        cin >> l >> r; l --; r --;
        p = i;
    }

    sort(b, b + q, [](str x, str y){
        if(x.l / B == y.l / B)
            return x.r < y.r;
        return x.l < y.l;
    });

    int l = 0, r = -1;
    for(int i = 0; i < q; i ++) {
        auto &[ql, qr, p] = b[i];
        while(r < qr) {
            add(++ r);
        }

        while(l > ql) {
            add(-- l);
        }

        while(r > qr) {
            rem(r --);
        }

        while(l < ql) {
            rem(l ++);
        }

        ans[p] = sum;
    }

    for(int i = 0; i < q; cout << ans[i ++] % MOD << '\n');
}