#include <bits/stdc++.h>
using namespace std;

const int zaharel = (int) 1e5 + 3;
const int mod = 666013;

int n, k, m;
int v[zaharel];
int ans[zaharel];
int aib[zaharel];
int last[zaharel];
vector < pair <int, int> > que[zaharel];

void read() {
    ifstream fin ("distincte.in");
    fin >> n >> k >> m;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (int i = 1; i <= m; ++i) {
        int l, r;
        fin >> l >> r;
        que[r].push_back( {l, i});
    }
}

inline void getMod (int& x) {
    while (x >= mod)
        x -= mod;
    while (x < 0)
        x += mod;
}

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

inline int query (int i) {
    int ret = 0;
    for (; i; i -= i & -i)
        ret += aib[i], getMod(ret);
    return ret;
}

void solve() {
    for (int i = 1; i <= n; ++i){
        sort(que[i].begin(), que[i].end());
        if (last[v[i]])
            update(last[v[i]], -v[i]);
        update(i, v[i]);
        last[v[i]] = i;
        for (const auto& it : que[i]){
            int l = it.first, from = it.second;
            ans[from] = query(i) - query(l - 1);
            getMod(ans[from]);
        }
    }
}

void print() {
    ofstream fout ("distincte.out");
    for (int i = 1; i <= m; ++i)
        fout << ans[i] << "\n";
}

int main() {
    read();
    solve();
    print();
}