#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, mod = 666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define cin fin
#define cout fout

int n, q, k, v[N];
long long aib[N], ans[N];
vector<pair<int, int>> en[N];
vector<int> fr[N];
void update(int pos, int val){
    for(; pos <= n; pos += (pos & -pos)){
        aib[pos] += val;
    }
}
long long query(int pos){
    long long res = 0;
    for(; pos > 0; pos -= (pos & -pos)){
        res += aib[pos];
    }
    return res;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        fr[v[i]].push_back(i);
    }
    
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        en[r].push_back({l, i});
        
    }
    for(int i = 1; i <= n; i++){
        auto it = lower_bound(fr[v[i]].begin(), fr[v[i]].end(), i);
        int pos = it - fr[v[i]].begin();
        if(pos == 0){
            update(1, v[i]);
            update(i + 1, -v[i]);
        }else{
            update(fr[v[i]][pos - 1] + 1, v[i]);
            update(i + 1, -v[i]);
        }

        for(auto j : en[i]){
            ans[j.second] = query(j.first);
        }
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] % mod << '\n';
    }
}